[baekjoon 2294] 동전 2- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2294

2294번: 동전 2

주어진 동전의 값을 이용해서 목표한 값을 동전 개수의 합으로 나타내는 경우 중 최소한의 동전 개수를 출력한다.

 

동전의 값보다 작은 숫자는 만들지 못한다.

동전의 값보다 큰 숫자는 크기가 n인 동전으로 구성할 수 있다.

그리고 그 이후에 크기가 n보다 큰 동전으로 그 숫자를 구성할 수 있다면 동전의 개수는 줄어든다.

 

즉, 5를 동전 1, 2, 5로 만들 수 있는 경우를 생각해보면 

 

동전 1을 이용한 최소 개수 : 1 + 1 + 1 + 1 + 1

동전 2를 함께 이용한 최소 개수 : 1 + 2 + 2 가 나온다.

하지만 동전 5가 등장하는 순간 동전 5 하나로 만들 수 있다.

 

즉 dp배열에 작은 동전부터 개수를 갱신해주고, 큰 동전이 나오면 기존 값과 큰 동전으로 갱신할 수 있는 경우 중 최솟값을 저장해주면 된다.

 

3 15

1 5 12의 경우 : 

 

동전 1을 사용  : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

동전 5를 포함  : 1 2 3 4 1 2 3 4 5  2   3  4   5  6  3

동전 12를 포함 : 1 2 3 4 1 2 3 4 5  2  3  1   2  3  4

 

큰 동전이 나오고, 그 동전을 이용할 수 있는 경우 갱신이 되는 점을 이용하면 된다. 그 수만큼 빼주면 남은 수의 배열엔 그 남은 수를 만들 수 있는 최소 경우가 저장되어 있기에 현재 배열도 최솟값이 된다.

dp [13] = dp [13-12] + 1 (동전 12) => 동전 12를 사용하면 13중 1이 남고 dp [1]엔 1을 만들 수 있는 경우 1이 저장되어있다.

 

#include <iostream>
#define INF 987654321
using namespace std;

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

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}

	for (int i = 0; i <= k; i++) {
		dp[i] = INF;
	}

	dp[0] = 0;

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

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

비슷한 문제로 www.acmicpc.net/problem/1699

1699번 제곱수의 합을 풀어보면 도움이 될 것이다. 이 문제와 차이점은 이룰 수 있는 값이 입력값으로 주어지는지, 제곱수로 정해져 있는지 차이다.