백준 2293 동전 2(c++)

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

2293번: 동전 1

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	vector<int>v(n);
	vector<int>dp(k+1);
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	dp[0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=v[i];j<=k;j++){
			dp[j]+=dp[j-v[i]];
		}
	}
	cout<<dp[k]<<'\n';
}

<풀이과정>

이 문제는 dp를 이용한 점화식으로 풀어야 한다.

예시 가치의 합 10 동전 1,2,5

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
1	1	2(dp[i]+dp[j-v[i])	2	3	3	4	5	5	5
1	1	2	2	4	5	6	7	8	10

1원짜리로 만들 수 있는 경우의 수는 1가지 뿐이다. 하지만 2원짜리부터는 1+1 , 2 총 두가지가 된다.

그래서 점화식을 dp[j]= dp[j]+dp[j-v[i]]와 같이 계산해줘야 한다. (2원짜리를 이용해서 7원을 만들 때, 1원짜리로 만든 경우 +1원짜리와 2원짜리를 이용해서 5원짜리를 만드는 경우) 

1+1+1+1+1+1+1

 

1+1+1+1+1

2+2+1

2+1+1+1