2293-동전1

2293-동전1

동전 시리즈 문제가 여러 종류가 있는데 이 문제는 동전의 개수가 무한하다는 전제 하에 목표 금액을 만들 수 있는 경우의 수를 묻는 문제이다. 

테스트케이스에 나와있는 1,2,5원 3종류의 동전으로 목표 금액 10원을 만들어보자. dp테이블은 'dp[a]=b : a원을 만들 수 있는 경우의 수 b가지' 라고 정의하자. 그러므로 최종 정답은 dp[k]가 될 것이다. 초기 상태는 dp[0]=1로 두자. 0원을 만들기 위해서는 아무 동전을 사용하지 않는 경우를 1가지라고 생각하면 된다. 그 다음 현재 coin[i]원의 종류로 j원을 만들려고 한다면 그 경우의 수는 어떻게 계산해야 할까. 일단 이전 상태인 (i-1)번째까지 구했던 경우의 수에다가 이번에(i)번째를 통해서 새롭게 만들 수 있는 경우의 수를 더하면 될 것이다. 예를 들어 이전까지 1원 동전을 사용했고, 현재는 2원으로 총 6원을 만드는게 목표라 한다면 그 경우의 수는 기존의 1원으로 6원을 만드는 경우의 수 + 이번에 2원 동전을 통해서 새롭게 6원을 만들 수 있는 경우의 수를 더하면 된다. 

점화식으로 표현해보면 dp[j]= dp[j] (기존 경우) + dp[j-coin[i]] (새로운 경우)라고 표현할 수 있다. 

동전 금액이 반드시 오름차순으로 저장되야 정답인줄 알았는데 순서를 바꿔도 Accept을 받았다. 생각해보니 for loop를 돌때 금액의 순서는 상관이 없다. 왜냐면 현재 보는 금액과 이전에 보았던 금액은 서로 영향을 끼치지 않는다(독립적이다).

#include<stdio.h>
int coin[111], dp[10001];
int main() {
    int n, k;    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &coin[i]);
 
    dp[0] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }
 
    printf("%d\n", dp[k]);
    return 0;
}