[C++][백준][2293] 동전 1 (DP)

🍋 문제링크

https://www.acmicpc.net/problem/2293

2293번: 동전 1

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 1116 KB

시간 : 0ms

🍉 Code

#include <stdio.h>

int main(){
	int n, k;
	int arr[109], dp[20009];

	scanf("%d %d", &n, &k);

	for(int i=0 ; i<n ; i++)
		scanf("%d", &arr[i]);

	for(int i=0 ; i<=k ; i++)
		dp[i] = 0;

	for(int i=0 ; i<n ; i++){
		if (arr[i]>k) continue;
		dp[arr[i]] += 1;
		for (int j = arr[i]+1 ; j<=k ; j++){
			dp[j] += dp[j-arr[i]];
		}
	}

	printf("%d\n", dp[k]);

	return (0);
}

🥝 메모

넘나 어렵...😢

<유의사항>

• if (arr[i]>k) continue; 안해주면 dp[arr[i]] += 1; 여기서 배열을 넘어감!!!!!!!!
• (이거 찾는데 1시간..걸림)
• 위의 문제 안생기게 하려면 로 수정하기

#include <stdio.h>

int main(){
	int n, k;
	int arr[109], dp[20009];

	scanf("%d %d", &n, &k);

	for(int i=0 ; i<n ; i++)
		scanf("%d", &arr[i]);

	for(int i=0 ; i<=k ; i++)
		dp[i] = 0;

	dp[0] = 1;
	for(int i=0 ; i<n ; i++){
		if (arr[i]>k) continue;
		//dp[arr[i]] += 1;
		for (int j = arr[i] ; j<=k ; j++){
			dp[j] += dp[j-arr[i]];
		}
	}

	printf("%d\n", dp[k]);

	return (0);
}

<문제풀이>

• 1 2 5를 이용해서 만들수 있는 모든 경우의 수

• dp 함수가 변해가는 과정