[백준][2293번][DP] 동전 1

동전 1

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

<코드>

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

<문제 푼 요령>

1. 이 문제는 다이나믹 프로그래밍 유형이기 때문에 현재의 값을 만드는데 과거의 값이 어떤 영향을 미치는지 알아야 합니다.

2. 동전의 가지수를 구하는 경우이기 때문에 예를 들어 동전 500원을 만드는 경우의 수는 단순히 500원을 만들던가 300원과 200원을 이용해서 만들수도 있습니다. 즉 Dp[i] = Dp[r]+Dp[i-r] 로 만들 수 있는 것입니다.

3. 하지만 이렇게 문제를 푸는 방법은 Dp[i]를 만들기 위해서 이전값을 전부 검색해서 더하기 때문에 시간이 생각보다 오래걸립니다. 

4. 더 나은 방법은 배열을 갱신해서 풀면 된다고 합니다.