백준 2294 - 동전 2

문제

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

2294번: 동전 2

 

풀이

동전의 종류가 n개이고 구하고 싶은 가치가 k 일때 f(n, k)를 n번째 동전부터 사용하여 k를 나타내는 최소의 동전 수 로 한다. 이런 식으로 f(n+1, k)... 를 불러서 문제를 해결 할 수 있다. 동전의 수를 N 이라하고 각 동전의 가치를 coin[i]로 하면 면 다음과 같은 점화식을 구할 수 있다. 동전의 범위는 0부터 N-1까지이다.

 

f(n, k) = {

    0 (n=N이고 k = 0)

    IMPOSSIBLE (n=N이고 k != 0)

    min( f(n+1, k), f(n, k-coin[i])+1 ) (k >= coin[n])

}

 

n=N일 경우엔 동전이 없다. 따라서 k=0일 때는 0을 리턴해주면 되지만 0이 아니게 되면 불가능하게 된다. 

f(n, k-coin[i])+1 은 현재 n번째 동전을 1개 쓸 경우인 (k - coin[i])에 대해서 최소 동전을 다시 구하는 식이다.

이 식은 (k >= coin[i])일 때만 가능하다. k가 coin[i]보다 작아질 경우 coin[i]로는 k를 나타낼 수 없다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, k;
int coin[100];
int dp[101][10001];
 
const int IMPOSSIBLE = 1000000000;
 
// n번째 부터 동전을 사용해서 k를 구하는 경우
int f(int n, int k)
{
    if (dp[n][k] != -1) return dp[n][k];
    if (n == ::n) return (k == 0 ? 0 : IMPOSSIBLE);
 
    int result = f(n + 1, k);    // n+1 번째 부터 동전을 사용할 경우
    if (k >= coin[n]) result = min(result, f(n, k - coin[n]) + 1);    // 현재 동전을 1개만 사용 한 것과 n+1 번째 부터 사용한 것을 비교
    dp[n][k] = result;
    return result;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n >> k;
 
    for (int i = 0; i < n; i++) cin >> coin[i];
    
    for (int i = 0; i <= n; i++)        // -1로 초기화 하기 때문에 n과 k까지 해준다.
        for (int j = 0; j <= k; j++)
            dp[i][j] = -1;
 
    int result = f(0, k);
    if (result == IMPOSSIBLE) cout << -1;
    else cout << result;
 
    return 0;
}