문제 설명

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

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

입력

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

출력

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

문제 풀이

dp는 슬슬 익숙해진 것 같아 이 문제까지만 풀고 다른 유형을 풀어보려 했는데, 이 문제를 아무리 생각해봐도 점화식을 잡지 못하였다. 결국 해설을 보았는데 보고도 이해를 잘 하지 못해 1시간 동안 해설을 보고있었다. 문제의 풀이 방식은 다음과 같다.
문제의 중요한 포인트는 두 가지이다. 첫째는 동전의 관점에서 봐야한다는 것이다. dp[4]를 4를 만드는 경우의 수라고 할 때 우리는 거기에 1원짜리 동전을 더해 5원을 만들 수 있다. 이 경우 dp[5]+=dp[4]가 된다. 5원을 만드는 방법은 이외에도 dp[3]에 2원짜리 동전을 더할 수도 있다. 이 경우 dp[5]+=dp[3]이 된다. 이런 식으로 dp배열을 증가시켜 나가는 것이 문제의 풀이이다.
하지만 이 문제에는 중요한 점이 하나 더 있는데, 두 번째 중요한 점은 바로 구성의 순수성이다. 문제를 읽어보면 같은 구성이지만 순서가 다른 것은 하나로 친다고 되어있다. 우리가 만약 1원과 2원짜리 동전으로 경우의 수를 세고, 각 dp배열의 숫자마다 동전의 종류를 모두 써서 카운팅한다고 가정하면, dp[1]은 1, dp[2]는 1원이 필요할 때와 2원이 필요할 때 두 경우므로 dp[1]+dp[0]=2가 될 것이다. 2를 만드는 경우의 수는 1+1,2 두가지므로 여기까지는 맞는 듯 싶다. 하지만 dp[3]을 만들 때엔 아까와 같은 방식으로 계산하면 dp[2]+dp[1]이 될 것이고 이는 dp[3]=3이 된다. 3을 만드는 경우의 수는 1+1+1,2+1 두 가지 뿐인데 오답이 나오는 것이다. 이 계산의 문제점은 2원짜리 동전을 사용하는 계산은 dp[3]+=dp[1]인데, 1원짜리 동전을 사용하는 계산인 dp[3]+=dp[2]에서 dp[2]에 이미 2원짜리를 쓰는 경우의 수가 들어가 있다는 점이다. 즉 이런 경우를 피하고 구성의 순수성을 지키기 위해서 우리는 1원짜리 동전을 쓰는 계산, 2원짜리 동전을 쓰는 계산을 순서대로 진행해야 함을 알 수 있다.
따라서 dp배열의 정확한 확장은 for(coins) for(index) dp[i]=dp[i-coin] 임을 알 수 있다. 앞으로 dp 문제를 풀 때에는 무조건 종이나 메모장을 키고 하나씩 카운팅 하면서 규칙을 찾아야겠다고 결심하게 되는 고난도 문제였다. dp 문제를 조금 더 풀어봐야겠다.

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,k;
    cin >> n >> k;
    vector<int> table;
    for(int i=0; i<n; i++) {
        int a; cin >> a;
        table.push_back(a);
    }
    int dp[10005]={0,};
    dp[0]=1;
    for(int num : table) {
        for(int i=1; i<=k; i++) {
            if(i-num>=0) dp[i]+=dp[i-num];
        }
    }
    cout << dp[k];
}