[Gold 5] 2294 동전 2

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

2294번: 동전 2

 

이 문제는 동전 1과 유사한 문제다.

단, 동전 1과 다르게 동전 합의 최소 개수를 구하는 문제다.

 

동전 합의 최소 개수를 구하기 위해선 그리드 알고리즘이나 DP를 사용하면 된다.

이 문제인 경우 동전의 가치가 배수 관계가 아니기 때문에 DP를 사용해야만 한다.

 

DP 식은 아래와 같다.

동전의 가치인 arr[i-1]에 따라 dp[j]를 구한다. 이때 arr[i-1]에 따라 dp[j]를 더 작게 구할 수 있다면 dp를 갱신한다.

 

위 식을 예제 표로 바꾸면 다음과 같다.

dp를 0으로 초기화 한 후 동전 1에 대해 경우의 수를 구한다.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 

동전 5에 대해 경우의 수를 구한다. 1~4를 구할 수 있는 경우는 없기에 5번째 부터 구한다.

0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3

 

동전 12에 대해 경우의 수를 구한다.

0 1 2 3 4 1 2 3 4 5 2 3 1 2 3 3

 

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

int N, K;
int arr[101];
int dp[10001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	for (int i = 1; i <= K; i++) dp[i] = 10001; 

	for (int i = 1; i <= N; i++) { 
		for (int j = arr[i-1]; j <= K; j++) { 
			dp[j] = min(dp[j], dp[j - arr[i-1]] + 1);
		}
	}

	if (dp[K] == 10001) cout << -1 << '\n';
	else cout << dp[K] << '\n';
}