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

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, k, ans;
int value[101];
int dp[10001];

int main() 
{
	cin >> n >> k;
	
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> value[i];
		
	}
		
	for (int i = 1; i <= n; i++)
	{
		for (int j = value[i]; j <= k; j++)
		{
			dp[j] += dp[j - value[i]];
		}
	}
	cout << dp[k];

}

 

풀이 방법

n개의 동전의 가치는 value배열에 저장합니다. 그리고 dp[0]은 초기값 1로 설정합니다.

for (int i = 1; i <= n; i++)
	{
		for (int j = value[i]; j <= k; j++)
		{
			dp[j] += dp[j - value[i]];
		}
	}

여기서 i는 1~n까지 반복문을 도는데 입력 예제 1로 설명을 드리겠습니다.

index	1	2	3
value	1	2	5

 

i가 1일때 j는 value[1]부터 value[k] = value[10] 까지 반복문을 돕니다.

그리고 dp[x]는 동전을 조합해서 만들 수 있는 조합의 수라고 합니다. 여기서 만약에 value[1]원을

추가해서 x원을 만들려면 어떻게 해야 할까요? 

점화식으로 나타내 보면 dp[x] += dp[x - value[i]]가 됩니다. 즉, 1원짜리 동전으로 만약 4원을 만들려면 3원을 만들 수 있는 조합의 수에서 1원을 더해주면 되겠죠? 따라서 dp[4] += dp[4 - 1]이 됩니다.

 

따라서 i가 1~3까지 반복문을 돌때 dp값의 변화를 살펴보면,

위와 같이 됩니다. 예시로 i가 2일 때 즉, value[2]인 2원짜리로 6원을 만든다고 생각해볼 때 6원은 4원에서 2원을 더해서 만들 수가 있습니다. 따라서 dp[6] += dp[6 - 2]이고 기존의 dp[6]이 1이였으므로 dp[6] = 1 + 3인 4가 됩니다. 이런 식으로 구하면 k원을 만들 수 있는 조합의 수를 구할 수 있습니다.

 

 

 

 

www.acmicpc.net/problem/2293

2293번: 동전 1