[백준][2294번][DP] 동전 2

동전 2

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

<코드>

#include <stdio.h>
 
 
int main(void){
 
    int n, k;
    int Dp[10001] = {};
    int coin[101];
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < n; i++){
        scanf("%d", &coin[i]);
 
        for (int j = 1; j <= k / coin[i]; j++)
        {
            int nowCoin = coin[i]*j;
            if (Dp[nowCoin] == 0)
                Dp[nowCoin] = j;
            else
                Dp[nowCoin] = Dp[nowCoin] < j ? Dp[nowCoin] : j;
 
        }
    }
 
    for (int i = 2; i <= k; i++)
    {
        for (int j = 1; j <= i / 2; j++)
        {
            if (Dp[j] != 0 && Dp[i - j] != 0){
                if (Dp[i] == 0)
                    Dp[i] = Dp[j] + Dp[i - j];
                else
                {
                    int temp = Dp[j] + Dp[i - j];
                    if (Dp[i] > temp)
                        Dp[i] = temp;
                }
            }
        }
    }
 
 
    if(Dp[k]==0)
        printf("-1\n");
    else
    printf("%d\n", Dp[k]);
 
}
 

<문제 푼 요령>

 1. 이 문제에서 중요한 것은 최소 개수를 만드는 것입니다.

 2. 그렇기에 처음 Dp[i] 배열은 0으로 초기화 되어있기 때문에 이 부분에 대해서는 예외 처리 해줍니다.

 3. 처음 먼저 각 숫자에 대해서 그 숫자에 배수로 Dp 배열을 채우고 이미 값이 들어가 있으면 min 값을 체크해 줍니다.

 4. 그후 2 ~~ K 까지 Dp[i] = Dp[j] + Dp[i-j] 로 만들어질수도 있기때문에 이걸 만들어가면서 최소값을 비교해줍니다. 여기서 중요한것 중 하나는 Dp[j]와 Dp[i-j] 중 하나라도 0이 포함된다면 Dp[i]는 만들 수 없는 숫자가 되는 거기 때문에 예외 처리 해줍니다.

 5. 이렇게 값을 구하면  Dp[k]에서 우리가 원하는 최소값을 구할수 있습니다.