Baekjoon 2293 (동전 1)

Baekjoon 2293, 백준 2293 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int n, k;
    scanf("%d %d",&n,&k);
    int* coins = new int[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&coins[i]);
    }

    // Solution by Dynamic Programming
    int dp[10001] = {0,};
    dp[0] = 1;  // initialization

    // overwrite array dp while increasing coin types
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= k; j++) {
            if(coins[i] <= j)   // use dp[0]=1
                dp[j] += dp[j-coins[i]];
        }
    }

    printf("%d\n", dp[k]);
    delete[] coins;
}

오랜만에 동적 계획법 (Dynamic Programming) 문제를 접하게 되었다.
dp[i] 를 i 원을 만들 수 있는 방법의 수로 놓고, 동전 종류를 한 개씩 늘려가면서 추가되는 방법들을 덮어쓰는(overwrite) 방식으로 해결하였다.

동적 계획법 문제의 경우에는 dp 배열을 생각보다 굉장히 단순히 설정하고,
어떻게 그 배열의 값들을 update 해줄까가 문제의 핵심이 되는 것 같다.