백준 2294 동전 2(c++)

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

2294번: 동전 2

<코드>

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

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int>v(n);
	vector<int>dp(k+1);
	dp[0]=0;
	for(int i=1;i<=k;i++){
		dp[i]=10000000;
	}
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	sort(v.begin(),v.end(),greater<int>());
	for(int i=0;i<n;i++)
	{
		for(int j=v[i];j<=k;j++)
		{
			dp[j] = min(dp[j],dp[j-v[i]]+1);
		}
	}
	if(dp[k]==10000000) cout<<-1;
	
	else cout<<dp[k];
}

<풀이 과정>

이 문제를 보자마자, 거스름돈 문제가 떠올랐다. 거스름돈 n원을 만들기 위해 최소 동전의 개수를 어떻게 만들어야 되는가에 대해서 고민해볼 수 있다. 일단 우선적으로 dp[0]=0(0원을 만들기 위해서는 동전이 0개 필요하기 때문에 dp[0]을 0으로 초기화해줘야 한다) 

우선 동전의 액면을 내림차순으로 정렬시켜준다 ex) 1, 5, 12일 때 12, 5, 1로 내림차순 정렬 시켜준다.

그리고 동전을 최소화하기 위해서 min(dp[j], dp[j-v[i](동전의 액면)]+1)로 표현했다.

ex) 동전의 합 9 동전의 액면 1,5,12

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
5	1	2	3	4	1(dp[5-5]+1)	2	3	4	5
12	x	x	x	x	x	x	x	x	x

이런 식으로 dp를 이용한 점화식을 통해 최적화된 해를 구할 수 있다.