[Baekjoon]백준 2293 동전 1(골드 4) - Python, C++

문제설명

문제를 살펴보면 그리디 알고리즘의 거스름돈 문제가 약간 생각나게 되는 문제이다

동적 프로그래밍 알고리즘의 핵심은 점화식을 찾는 것이다

그래서 점화식을 어떻게 만들어서 어떻게 값을 넣을지 고민해보았는데, index를 n원을 만드는 경우의 수로

설정하여 점화식을 찾아보고자 노력하였다

 

예를 들어 dp[2]의 경우라면 2원을 만드는 경우의 수, dp[5]라면 5원을 만드는 경우의 수가 들어가도록 설정하였다

이제 이 값을 어떻게 설정할 지가 고민인데, 일단 예제를 보고 직접 값을 넣어가면서 규칙을 찾아보았다

우선, 동전 1을 통해 만들수 있는 경우의 수는 모두 1이다

이후 동전 2를 사용한다고 가정할 때, 동전 2를 사용해서 1원을 만들수는 없기 때문에

dp[1]의 값은 더이상 갱신되지 않고 값이 확정된다는 사실을 알 수 있다

 

그렇다면 dp[2]의 값은 어떻게 될까?

dp[2]의 경우 1+1, 2의 경우로 총 두가지임을 확인할 수 있다

dp[3]의 경우 1+1+1, 1+2로 총 두가지임을 확인할 수 있다

근데 이를 dp[1]부터 나열하여 확인해보면(동전 2원인 경우)

dp[1] => 1                                     → 1

dp[2] => 1+1, 2                             → 2

dp[3] => 1+1+1, 1+2                     → 2

dp[4] => 1+1+1+1, 1+1+2, 2+2     → 3

무언가 규칙이 존재한다

결국 2원을 사용하여 4원을 만들게 되면 2원을 만드는 과정(경우의 수)가 필수적으로 포함되게 되어있다

그 말인 즉슨 dp[i] = dp[i] + d[i-coin]이라는 점화식이 나오게된다

이전에 계산한 값을 이용하여 새로운 값을 갱신하게 된다

 

coin의 크기보다 낮은 index는 갱신이 이루어지지 않는다는 점과 해당 점화식을 통해 

코드를 작성하면 다음과 같다

import sys
input = sys.stdin.readline

num, coin = map(int, input().split())
cost = []
for _ in range(num):
    cost.append(int(input()))
    
dp = [0 for _ in range(coin + 1)]
dp[0] = 1
for cn in cost:
    for k in range(cn, coin + 1):
        dp[k] += dp[k-cn]

print(dp[coin])

C++로도 작성해보았는데, dp배열 초기화 부분을 까먹고 안 넣었다가 꽤 오랫동안 오류와 싸웠다...

배열 초기화를 생활화하자 ㅜㅜ

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int num, coin;
    cin >> num >> coin;
    int cost[100];
    for(int i = 0; i < num; i++)
        cin >> cost[i];
    
    int dp[10001] = {0};
    dp[0] = 1;
    for(int i = 0; i < num; i++){
        for(int j = cost[i]; j < coin+1; j++) {
            dp[j] += dp[j-cost[i]];
        }
    }

    cout << dp[coin] << endl;
    
    return 0;
}