[C++] BAEKJOON 2293 동전 1

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

2293번: 동전 1

동적계획법을 활용한 문제입니다. dp[i] 를 i 원에 대해서 주어진 동전으로 만들 수 있는 경우의 수라고 정의했습니다. 처음에는 동전을 하나만 사용하여 계산할 수 있는 경우의 수를 채우고, 이를 활용하여 동전 2개를 사용했을 경우, 3개, 4개 … 다음과 같이 늘려나가게 됩니다.

주어진 문제의 예시 처럼 1,2,5 원으로 10원을 만들려고 한다면

10원을 만드는 경우의수 = 9원까지의 경우의 수(1원 추가) + 8원까지의 경우의수 (2원 추가) + 5원까지의 경우의 수(5원 추가)

다음과 같은 관계식을 세울 수 있고 이를 점화식으로 세우면 다음과 같습니다.

dp[j] += dp[j-coin[i]];

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int coin[101];
    int dp[10001] = {0};
    
    int n,k;
    cin >> n >> k;
    
    for (int i=1;i<=n;i++){
        cin >> coin[i];
    }
    
    dp[0] = 1;
    
    for (int i=1;i<=n;i++){
        for (int j=1;j<=k;j++){
            if (j-coin[i] >= 0)
                dp[j] += dp[j-coin[i]];
        }
    }
    cout << dp[k] << "\n";
    
    return 0;
}