동전 1 2293

문제

접근 방법

예제에서는 1원, 2원, 5원으로 10원을 만드는 경우를 줬다.
1원인 경우부터 생각해보자.
k=1 1개 1원 1개
k=2 2개 1원 2개, 2원 1개
k=3 2개 1원 3개, 2원 1개 + 1원 1개
k=4 3개 1원 4개, 2원 1개 + 1원 2개, 2원 2개
k=5 4개 1원 5개, 2원 1개 + 1원 3개, 2원 2개 + 1원 1개, 5원 1개
k=6 5개 1원 6개, 2원 1개 + 1원 4개, 2원 2개 + 1원 2개, 5원 1개 + 1원 1개, 2원 3개
k=7 6개 1원 7개, 2원 1개 + 1원 5개, 2원 2개 + 1원 3개, 5원 1개 + 1원 2개, 2원 3개 + 1원 1개 , 5원 1개 + 2원 1개
k=8 7개 1원 8개, 2원 1개 + 1원 6개, 2원 2개 + 1원 4개, 5원 1개 + 1원 3개, 2원 3개 + 1원 2개 , 5원 1개 + 2원 1개 + 1원 1개, 2원 4개
k=9 8개 1원 9개, 2원 1개 + 1원 7개, 2원 2개 + 1원 5개, 5원 1개 + 1원 4개, 2원 3개 + 1원 3개 , 5원 1개 + 2원 1개 + 1원 2개, 2원 4개 + 1원 1개, 5원 1개 + 2원 2개
k=10 10개 1원 10개, 2원 1개 + 1원 8개, 2원 2개 + 1원 6개, 5원 1개 + 1원 5개, 2원 3개 + 1원 4개 , 5원 1개 + 2원 1개 + 1원 3개, 2원 4개 + 1원 2개, 5원 1개 + 2원 2개 + 1원 1개, 5원 2개, 2원 5개

1원만 있는 경우는 1, 1, 1, 1, 1, 1, 1, 1, 1, 1이다.
2원도 있는 경우는 1, 2, 2, 3, 3, 4, 4, 5, 5, 6이다.
5원도 있는 경우는 1, 2, 2, 3, 4, 5, 6, 7, 8, 10이다.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1이다.
1, 2, 2, 3, 3, 4, 4, 5, 5, 6이다.
1, 2, 2, 3, 4, 5, 6, 7, 8, 10이다.

2원일 때 n원의 경우의 수는 1원일 때 n원의 경우의 수 + 2원일 때 n-2원의 경우의 수인 것을 확인할 수 있다.
5원인 경우에도 통하는 것을 볼 수 있다.

기존 조합을 유지해가며 새로운 값의 조합을 넣기 위해선 해당 값만큼의 여유가 필요하기 때문에 생긴 공식인 것 같다.

즉 7원의 경우로 예시를 들면 2개 1원 2개, 2원 1개에 5원을 붙이면 2원과 1원만으로 이루어진 조합에 추가할 수 있으니 2원까지의 7원을 만드는 조합 + 5원까지의 2원을 만드는 조합 (5원을 추가하므로)인 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> dp(k + 1), coins;
    while (n--)
    {
        int coin;
        cin >> coin;
        coins.push_back(coin);
    }
    dp[0] = 1;
    for (int coin : coins)
    {
        for (int i = coin; i <= k; ++i)
        {
            dp[i] += dp[i - coin];
        }
    }
    cout << dp[k];
    return 0;
}

풀이

DP 문제는 규칙 찾기가 중요한 것 같다. '이런 방법 아닌가?'라는 예측은 되는데 식을 도출하는 데는 좀 걸리는 것 같다.