백준 2294번, 동전 2(C, C++)

2294번: 동전 2 (acmicpc.net)

2294번: 동전 2

해당 문제는 다이나믹 프로그래밍으로 문제를 해결하였습니다.

 

 예제는 3가지의 동전{1, 5, 12} 과 15원을 만드는데 최소 동전 수를 구하는 문제입니다.

1-> 1                 dp[1] = 1

2 - > 1, 1           dp[2] = 2

3 -> 1, 1 , 1       dp[3] = 3

4 -> 1, 1, 1, 1    dp[4] = 4

5 - > 1, 1, 1, 1, 1   dp[5] = 5

        or

        5

위 예시에서 동전 1원인 경우에 dp[i]는 dp[i-1]의 동전 수에서 +1이 된 것을 알 수 있습니다.

다만 dp[5]인 경우, dp[4] 동전수 + 1이 된 것이 아닙니다,  저희가 구해야 하는 것은 최소 동전 수입니다.

아무것도 없는 dp[0]에서 + 1이 된 것을 알 수 있습니다.

동전을 배열 coin로 정의하면, 점화식으로 표현할 수 있습니다.

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

#include<iostream>
#include<algorithm>

#define INF 10001

using namespace std;

int main(){
    int N;
    int K;
    int coin[101];
    int dp[10001];
    dp[0] = 0;

    cin>>N>>K;
    for(int i = 1; i <= K; i++){
        dp[i] = 10001;
    }
    
    for(int i = 1; i <= N; i++){
        cin>>coin[i];    
    }

    for(int i = 1; i <= K; i++){
        for(int j = 1; j <= N; j++){
            if(i - coin[j] >= 0){
                dp[i] = min(dp[i-coin[j]] + 1, dp[i]);
            }
        }
    }
    if(dp[K] == 10001){
        cout<<-1;
    }else if(dp[K] != 10001){
        cout<<dp[K];
    }
   return 0;    
}