백준 - 2293 동전 1

[문제 링크]

DP문제이다. 정말 내 머리가 DP에서 틀에 박혔다는 생각이 든 문제였다. 원래는 DP[V] = DP[V] + DP[V-COIN[I]]와 같은 점화식으로 문제를 풀어나갔는데.

이 식의 문제점은 다른 순서지만, 같은 종류의 동전을 사용한 것도 모두 다른 값으로 취급해 카운트를 하는 것 같았다. 그래서 그냥 단순하게 위와 같은 방식으로 문제를 풀 경우 출력값이 엄청 크게 나왔다..

그래서 내가 원래 풀었던 것과 반복을 다른 방법으로 진행해야 하는데, 그것은 각 값 별로 방법의 수를 구하는 것이 아니라, 동전 별로 각 값에 대한 방법의 수를 구하는 것이다.

밑의 코드는 원래 방식대로, 값을 기준으로 재귀를 진행한 코드이다. 1,1,1,2와 2,1,1,1과 같은 같은 종류지만 다른 순서로 인것들도 모두 다른 경우로 취급해 엄청 큰 값이 나온다. 

각 동전의 경우에 따른 경우의 갯수를 cache의 2차원 배열로 추가하면 문제 해결이 가능하고, 실제로도 이렇게 답을 구했었지만 이 경우 문제의 메모리 제한 4mb를 초과해버린다.

#include <cstdio>
#include <cstring>
int n,coin[101],k,cache[10001];
//사용한 동전 갯수가 같으면 같은 경우이다. 
int dp(int value){
    //기저사례 num == k일때 
    if(value==0) return 1;
    //기저사례 2, n을 넘어설때, 0
    if(value<0) return 0;
    int& ret = cache[value];
    if(ret!=-1) return ret;
    ret = 0;
    //점화식  
    for(int i=0;i<n;i++){
        if(value-coin[i] >= 0)
            ret = ret + dp(value-coin[i]);
    }
    return ret;  
}
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    printf("%d",dp(k));
}

밑은 각 동전별로 경우의 수를 구한 코드이다.

#include <cstdio>
int n,coin[101],k,cache[10001]={0,};
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 1;
    
    //각 동전별로 값마다 경우의 수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i])
                cache[j] += cache[j-coin[i]];
        }
    }   
    printf("%d",cache[k]);
}

코드가 훨씬 간결하고 직관적이다. DP에 대한 학습은 아직 더 필요한거같다.