백준 2294번 동전 2 - C++ 풀이

---

 

1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수
2. dp(price) = min(1 + dp(price - coin[i]))

 

1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수

 dp(price)를 위와 같이 정의하자. 기저 사례는 price = 0일 때 return 0.

 

2. dp(price) = min(1 + dp(price - coin[i]))

 각 동전의 개수는 무한하므로 price원을 만들기 위해 이번에 사용할 동전만 골라주면 된다. i번째 동전을 사용하기로 했을 때 dp(price) = 1 + dp(price-  coin[i]). i = 0~(N-1)까지 각 동전을 고르는 모든 경우를 탐색한 뒤, 그중 최솟값을 찾으면 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int INF = 987654321;

int N, K;
int coin[101];
int cache[10001];

// dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수
int dp(int price) {
    if (price == 0) return 0;
    
    int& ret = cache[price];
    if (ret != -1) return ret;
    
    ret = INF;
    for (int i=0; i<N; i++) {
        if (coin[i] <= price) ret = min(ret, 1+dp(price-coin[i]));
    }
        
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N >> K;
    for (int i=0; i<N; i++) cin >> coin[i];
    
    int ans = dp(K);
    
    if (ans == INF) cout << -1;
    else cout << ans;

    return 0;
}