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

 

#include <iostream>

using namespace std;

int coin[101];
int DP[10001];

int main(void)
{
	int n=0;
	int k=0;
	
	cin>>n>>k;
	
	for(int i=1; i<=n; i++)
	{
		cin>>coin[i];
	}
	
	DP[0]=1;
	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=k; j++)
		{
			if(j-coin[i]>=0)
			{
				DP[j]+=DP[j-coin[i]];
			}
			
		}
	}
	
	cout<<DP[k];
	 
	return 0;
}

n가지의 동전이 주어졌을 때 적절히 조합해서 k원이 되게 만들고 그 경우의 수를 출력하는 문제이다.

 

이 문제와 비슷한 문제를 예전에 접한 적이 있다. 그 문제에서는 거스름돈을 기준으로 시작했었다. 그래서 이 문제도 거스름돈을 기준으로 두고 풀려고 시도하였으나 아무리 생각해도 경우의 수를 출력하는 방법을 떠올리지 못했다. 그래서 구글링 했더니 다른 분들은 거스름돈을 기준으로 두지 않고 동전을 기준으로 두었다는 사실을 알게 되었다. 아..... 왜 이 생각을 못했을까 ㅠㅠ(너무 거스름돈에 꽂혀버린 건가 ㅋㅋ)

 

어쨌든 문제를 푸는 방법은 다음과 같다.

일단 가장 작은 동전을 기준으로 DP를 업데이트한다.

 

1원

 

0을 1로 초기화한 이유는 DP[j-coin[i]]를 보면 알 수 있다. 예(DP[1-1], DP[2-2], DP[5-5])는 1이 되어야 하기 때문 

DP[1] 1원 하나의 조합 필요, DP[2] 2원 하나의 조합 필요, DP[5] 5원 하나의 조합 필요.

아무것도 없는 허공에 추가한다고 생각하자.

 

 

2원

 

5원

정말 허무할 정도로 코드가 간단하다

조금 더 분발해야겠다.