[백준] 2293 - 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

배낭문제와 유사한 풀이방식이다. dp[k]는 k원이 되는 동전의 구성 경우의 수이다. 이를 중복없이 계산하기 위해서 1번째 동전을 1~k원까지 채워넣고 그리고 2번째, 3번째 ... n번째 동전까지 경우의 수를 고려한다. 그렇게 되면 j번째 동전에서 그 전 동전이 이미 반영이 다 되고 더 이상 반영이 안되기에 중복이 안되게 된다. 그래서 dp[j]에 dp[j - arr[i]] 를 계속 더해주고 dp[k]를 출력하면 답이다.

#include <iostream>
using namespace std;

int dp[10001];
int arr[101];
int n, k;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    dp[0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            if (j >= arr[i])
                dp[j] += dp[j - arr[i]];

    cout << dp[k] << "\n";
    return 0;
}