백준 / 2294 동전 2 C++

www.acmicpc.net/problem/2294

2294번: 동전 2

전형적인 dp문제이다. 

우선 0~k원까지 전부 inf로 초기화 한다. 그리고 dp[동전 가치]=1로 잡는다. (1개로 만들수 있으므로)

그러면 점화식이 다음과 같다.

 

dp[ j + coin[i] ] = min( dp[ j + coin[i] ], dp[ j ] + 1)

여기서 j는 구하고자 하는 가치이다. 

우선 우리는 dp를 inf로 초기화하였고, 동전의 개수 제한이 없으므로, i번째 동전을 1개씩 더하여 그 가치를 만들 수 있으면 +1을 하면 된다. 

그리고 j+coin[i] > k 를 만족하면 그 뒤 결과는 coin[i]를 더해도 k를 다 넘으므로 break 시킨다.  

이를 반복하면 된다.

ex) dp[6] = inf  =>  동전 가치가 1인 녀석을 반복 => dp[6] = 6 => coin=5일 때, dp[5]=1

=> dp[6] = min(dp[6], dp[5]+1) = 2

 

코드를 보는게 더 이해가 잘 될 듯 싶다. 

 

코드는 다음과 같다.

#include<iostream>
#include<algorithm>

using namespace std;

int n, k;
int coin[101];
int dp[100001];


int main()
{
	cin >> n >> k;
	
	int inf = 987654321;
	for (int i = 0; i <= k; i++)
		dp[i] = inf;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		coin[i] = num;
		dp[num] = 1;
	}

	for (int i = 0; i < n; i++) {
		for (int j = coin[i]; j <= k; j++) {
			if (j + coin[i] > k)
				break;
			dp[j + coin[i]] = min(dp[j + coin[i]], dp[j] + 1);
		}
	}

	if (dp[k] == inf)
		cout << -1;
	else
		cout << dp[k];
}