동전 1

문제 링크

사실 평범한 배낭 문제보다 이 문제가 더 직관적으로 떠올리기 쉽기 때문에 이쪽을 먼저 배우는게 일반적이다. 0/1 Knapsack이 아닌 Knapsack 문제라고 하면 보통 물건의 개수가 무한인 배낭 문제를 떠올리는 경우가 더 많다. 이 문제는 그 하위 호환으로, 별도의 물건 가치 없이 도달 할 수 있는 경우의 수만 세면 된다.

발상

이전 문제들과 다르게 물건(동전)의 개수가 무한이다. 이것은 이전 동전을 사용한 경우뿐만이 아니라 현재 동전을 사용해 만든 무게에도 현재 동전을 다시 사용해 새로운 무게를 만드는 것이 가능하다는 의미이다. 예를들어 1 2 3원 짜리 동전이 있을 때, 이전 0/1 Knapsack 문제에서는 2원 동전을 이용해 만든 2라는 가치에 또 다시 2원을 추가할 수는 없었지만, 이 문제는 동전의 개수가 무한하기 때문에 2원의 동전을 이용해 만든 2라는 가치에 2원 동전을 다시 사용해 4라는 가치를 만드는 것이 유효하다. 다시 말해, 이전 동전인지 현재 동전인지 구분이 필요하지 않다. 따라서 인자는 동전의 가치 하나밖에 없다. 몇번째 동전까지 사용해 만든 가치인지는 확인할 필요가 없다.

기저 사례는 가치가 0인 경우, 즉 동전을 선택하지 않은 경우 1가지이다.

점화식

$$\{\begin{array}{l}{n}_j=\text{가치 j를 만들 수 있는 경우의 수}\\ v_i=\text{i번째 동전 가치}\end{array}$$ $$n_j=\sum _{i=1}^k{n}_{j-v_i}$$

코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {    
    int n, k; cin >> n >> k; vector<int> arr(n + 1), dp(k + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[0] = 1; // 무게 0인 경우 기저 사례
    for (int i = 1; i <= n; i++) {        
        for (int j = arr[i]; j <= k; j++) {
            dp[j] += dp[j - arr[i]];
        }
    }
    cout << dp[k];
    return 0;
}