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

동전 2

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

<코드>

#include  <stdio.h>
 
 
int main(void)
{
   
    int N,K;
    int coinC[10001]={0,};
    int coin[101]={0,};
 
    scanf("%d %d",&N,&K);
 
    for(int i=0;i<N;i++)
    {
        scanf("%d",&coin[i]);
        if(coin[i]>10000)
            continue;
         
        coinC[coin[i]]=1;
    }
     
    for(int i=1;i<=K;i++){
        for(int j=0;j<N;j++)
        {
            if(i-coin[j]<0) // 범위를 넘어감 
            {
                continue;
            }
            else{
                if(coinC[i-coin[j]]==0) // 만들수 없는 범위다. 
                    continue;
                else{
                    if(coinC[i]==0)
                        coinC[i] = coinC[i-coin[j]] +1;          
                    else
                        coinC[i] = (coinC[i] < (coinC[i-coin[j]] +1)) ?  coinC[i] : (coinC[i-coin[j]] +1);
                                
                }
                 
            }
   
        }
         
    }
     
    if(coinC[K]==0)
        printf("-1\n");
    else
        printf("%d\n",coinC[K]);
     
    return 0;
}

<문제 푼 요령>

 1. 이 문제는 각 값어치당 만들 수 있는 동전의 최소값을 DP 테이블로 만들어서 푸는 문제이다.

 2. 즉 우리가 원하는 값까지 차례대로 DP 테이블을 채워가면서 만들어 원하는 값을 구하면 된다.

 3. 채워가는 경우를 예를 들어서 한 코인의 가치를 K라고 하고 우리가 원하는 값이 M 이라고 하면 우리는 DP[M] = DP[M-K] + 1 이 최소값이 될 수 있게된다. 하지만 다양한 가치를 가진 코인이 있기 떄문에 이 코인의 경우를 다 따져서 그 중 최소값을 DP[M]에 넣어주면 된다.

 4. 우리가 가진 코인의 조합으로 만들수 없는 경우를 찾기위해 처음의 배열을 0으로 초기화하고 코인 한개만 들어갈 경우를 미리 1로 만들어 놓았다. 만약 위의 예시되로 하자면 DP[M-K] 자체가 0이라고 가정하면 이 경우는 K라는 값어치를 가진 코인을 가지고는 M값어치를 가지는 경우의 수를 만들 수 없다라고 생각할 수 있다.

 5. 그리고 내가 문제를 풀다가 실수 해서 자꾸 틀린경우가 있는데 바로 코인의 값어치가 10000을 넘어버려서 런타임 에러가 나는 것이였다.