[백준] 2293번 동전 1 C++ 코드

코드

#include <iostream>

using namespace std;

int n,k,a[103], dp[10003];

int main() {
    cin >> n >> k;
    dp[0] = 1; // 0원을 만드는 경우의 수는 1
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        for(int j = a[i]; j <= k; j++) { // a[i]를 사용할 수 있는 j부터 최대 k까지
            // j를 만드는 방법 중 하나는 j - a[i]원에서 a[i]원을 더하는 것
            // 따라서 j원을 만드는 경우에 j - a[i]원을 만드는 경우의 수를 더함
            dp[j] += dp[j - a[i]]; 
        }
    }
    cout << dp[k] << '\n';
    return 0;
}

풀이

j가 a[i] 이상이어야 a[i]원부터 시작해서 k까지의 값을 대상으로 할 수 있다. dp[j]는 j원을 만들 수 있는 경우의 수를 의미한다. 그리고 dp[j - a[i]]는 j - a[i]원을 만드는 경우의 수를 의미한다. 만약 j - a[i]를 만들 수 있다면 a[i]원 동전을 이용해서 j를 만들 수 있다. 따라서 j원을 만드는 경우의 수에 j - a[i]원을 만들 수 있는 경우의 수를 더해준다.