백준 - 2294 동전 2

[문제 링크]

동전1에서 이어지는 문제다. 동전1은 경우의 갯수를 구하는 것이라면, 동전2 문제는 해당 경우에 사용되는 동전의 갯수를 구하는 것이다.

예를 들어 4원까지 동전 1,2만을 이용해서 갯수를 구하는 경우를 그려서 점화식을 구해보면

	1 동전 갯수	2 동전 갯수	DP(V)
1일 때 DP(1)	1 = DP(1-1)+1		1
2일 때 DP(2)	2 = DP(2-1)+1	1 = DP(2-2)+1	1
3일 때 DP(3)	3 = DP(3-1)+1	2 = DP(3-2)+1	2
4일 때 DP(4)	4 = DP(4-1)+1	2 = DP(4-2)+1	2

즉 DP(V) = min(DP(V), DV(V-COIN(i))+1) 의 점화식을 구할 수 있다.

다만 비교의 대상을 지정해야 하므로, 아무 값도 입력이 되어있지 않았을 때엔 최소 최적값 비교를 할 수 없기 때문에 DP(N) = DP(N- COIN(i)) + 1로 초기화 해주어야 한다.(초기화를 안해주면 DP(0)=0이므로 출력값은 0만 나온다..)

지금 동전 갯수를 구할 값이 초기화 된 값인지 아닌지, 이를 구하는데 필요한 이전 값이 초기화 되어있는지 조건을 걸어줘서 문제를 풀면 된다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algoritm> 
using namespace std;
int n,coin[101],k,cache[10001]={0,};
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 0;
    //각 동전별로 해당 값을 구하는데 드는 최소 횟수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i] && cache[j-coin[i]]!=-1){
                //아무 값도 입력이 안됬을 경우엔 동전의 갯수를 초기화해준다. 
                if(cache[j]==-1) 
                    cache[j] = cache[j-coin[i]]+1;
                //점화식, 값이 입력되어있으면 이전값과 비교해서 최소값을 넣어준다. 
                else
                    cache[j] = min(cache[j],cache[j-coin[i]]+1);
            }
        }
    }   
    printf("%d",cache[k]);
}