BOJ 2293번, 동전 1

유명하고, 간단한 DP문제입니다. 

가치가 X원이 되는 모든 경우의 수를 A(x)라고 했을 때,

입력받은 동전이 1, 2, 5원이고 10원을 만든다고 하면 (예제 1)

A(10)은 A(9)+1원, A(8)+2원, A(5)+5원이라고 할 수 있고,

A(9) = A(8) + A(7) + A(4)

A(8) = A(7) + A(6) + A(3)

A(5) = A(4) + A(3) + A(0)  

 cf) A(0)=1

...

이런식으로 여러가지의 점화식이 생깁니다.

중복되는 항이 많으므로, Dynamic Programming 기법을 사용해 문제를 풀면 아래의 소스코드와 같이 풀 수 있습니다.

#include <iostream>
 
using namespace std;
 
typedef long long LL;
LL N, K;
 
LL method[10001];
 
int main(){
    cin >> N >> K;
 
    method[0] = 1;
    for (int i = 0; i < N; i++) {
        int coin;
        cin >> coin;
 
        for (int j = coin; j <= K; ++j)
        {
            method[j] += method[j - coin];
        }
    }
 
    cout << method[K];
    return 0;
}