C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 2293번:동전1 답

D[i][j] = i개의 동전을 활용하여 j원을 만드는 경우의 수

  1.A[i]를 사용하는 경우 - > A[i-1]까지의 동전을 사용하여 j-A[i]원을 만들어야함 : D[i][j] += D[i-1][j-A[i]]

  2.A[j]를 사용하지 않는 경우 - > A[i-1]까지의 동전을 사용하여 j원을 만들어야함 : D[i][j] += D[i-1][j]

D[i] += D[i-1][j-A[i]] + D[i-1][j] 이는 1+1+2, 2+1+1, 1+2+1를 모두 다른 경우로 친다.

그러므로 이를 막기 위해 D[i] += D[i-A[j]]

#include <iostream>
using namespace std;
int n, k, a[101], d[10001];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    d[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
 
            if (a[i] <= j)
                d[j] += d[j - a[i]];
        }
    cout << d[k];
}