백준 2293 동전1

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n가지 종류의 동전으로 k원을 만들 수 있는 경우를 구하는 문제입니다. dp를 이용하여 가장 금액이 작은 동전으로 만들 수 있는 경우들을 각각 저장하며 문제를 해결하여야 합니다. 예를들어 문제의 예시인 1 2 5 원짜리 동전이 있고 10원을 만드는 가지를 구하려면 1원으로 1~10원을 만드는 경우를 모두 갱신하고 그다음 2원을 사용하여 갱신하는 경우를 더해주며 5원까지 가면 각각 금액을 만드는 모든 경우를 생각 할 수 있습니다.

 

따라서 dp[k] = dp[k] + dp[k-coin[i]] 라는 점화식이 나오게 됩니다. 식의 의미는 k원을 만드는데 i번째 동전을 사용하는 경우 (i보다 이전 동전들을 사용해서 만든 경우는 이미 저장되어 있습니다)라고 생각 하시면 됩니다.

저도 처음에는 이해하기가 어려웠는데 표나 그림을 그려서 생각해보면 조금더 수월하게 이해가 될 수 있습니다. 

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n,k;
	cin >> n >> k;
	int dp[10001] = {0, };
	int coin[101] = {0, };
	
	for(int i = 0; i < n; i++)
		cin >> coin[i];
	
	dp[0] = 1;
	
	for(int i = 0; i < n; i++) {
		for(int j = coin[i]; j <= k; j++) 
				dp[j] = dp[j] + dp[j-coin[i]];
	}
	
	cout<<dp[k];
	return 0;
}