[백준] 2293

동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

풀이

#include <iostream>

int dp[10001];
int v[101];

int main(void) {
    int n, k;

    std::cin >> n >> k;
    for (int i = 0; i < n; i++) std::cin >> v[i];

    dp[0] = 1;
    for (int j = 0; j < n; j++) {
        for (int i = 1; i <= k; i++) {
            if (i >= v[j]) dp[i] = dp[i] + dp[i - v[j]];
        }
    }

    std::cout << dp[k];
}

반성회

우선 dp[0]은 0이다

0원을 맞추는 데에는 동전이 0개 필요하므로 가짓수가 1이기 때문

 

1원짜리 동전만을 이용하여 금액을 낼 수 있는 가짓수는 위와 같다

금액이 0원일 때는 1원짜리 동전으로 지출할 수 없으므로 그대로 1이 되고

나머지 경우에는 지출할 수 있는 가짓수가 dp[i - 1]과 같으므로 (i - 1원을 만드는 경우에서 동전 1개만 더하면 되므로 가짓수가 같다)

dp[i] + dp[i - 1] 이 되되 dp[i] 는 해당 시점에서 0이므로 결과적으로 dp[i - 1] = 1으로 채워진다

 

1원짜리 동전과 2원짜리 동전을 이용하여 금액을 낼 수 있는 가짓수를 계산해보자

2원짜리 동전으로 금액을 만들 수 있는 경우는 2원 이상밖에 없으므로 0원, 1원의 경우에는 이전 값을 그대로 가져온다

그 외에는 마찬가지로 지출할 수 있는 가짓수가 dp[i - 2]와 같으므로 (i - 2원을 만드는 경우에서 동전 1개만 더하면 되므로 가짓수가 같다)

이를 앞서 1원으로 금액을 지출하는 경우의 수였던 dp[i]에 더해서 두 가지 경우를 모두 구해준다

 

마찬가지로 1원짜리 동전, 2원짜리 동전, 5원짜리 동전을 이용해서 금액을 낼 수 있는 가짓수를 계산한다

5원짜리 동전으로 금액을 만들 수 있는 경우는 5원 이상밖에 없으므로, 0 ~ 4원의 경우에는 이전 값을 그대로 가져온다

그 외에는 마찬가지로 지출할 수 있는 가짓수가 dp[i - 5]와 같으므로 (i - 5원을 만드는 경우에서 동전 1개만 더하면 되므로 가짓수가 같다)

이를 앞서 1, 2원으로 금액을 지출하는 경우의 수였던 dp[i]에 더해서 세 경우를 모두 구해준다

 

기존에 생각했던 dp와 좀 달라서 많이 어려웠던 문제였다..