[백준 2293번] 동전 1 (C++, Python3)

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

2293번: 동전 1

이번 포스트에서는 백준 알고리즘 문제인 동전 1을 포스트하겠습니다.

 

해당 문제는 solved.ac 기준 골드 5에 위치한 문제입니다.

 

먼저 문제입니다.

 

N가지의 동전과 K원을 입력받고 K원을 만들 수 있는 경우의 수를 출력해야합니다.

 

해당 문제는 K원을 만드는 경우의 수를 찾는 문제입니다.

따라서, N가지 동전으로 K원을 만들 때, N - 1개의 동전으로 만들 수 있는 경우의 수를 합산하여야합니다.

그렇기 때문에 DP로 문제를 해결합니다.

 

3 10
1
2
5

문제에서 주어진 위 입력 예제로 볼 때, N이 3, K는 10이고, 동전은 각각 1원, 2원, 5원입니다.

그럼 다음 dp 테이블을 작성할 수 있습니다.

 

n/k 1 2 3 4 5 6 7 8 9 10
1   1 1 1 1 1 1 1 1 1 1
2   1 2 2 3 3 4 4 5 5 6
5   1 2 2 3 4 5 6 7 8 10

 

먼저 1원짜리 동전으로 1~10원을 만든다고 했을 때, 가능한 경우의 수로 채웁니다.

그다음 2원짜리 동전으로 1~10원을 만들 때, i원을 만들기 위한 경우의 수는 dp[i] + dp[i - 현재 동전의 가치] 로 일반화됩니다.

 

EX) 5원의 경우 (1,1,1,1,1),(1,1,1,2),(2,2,1) 의 세가지 경우의 수가 존재합니다. 1원만으로 사용하는 경우의 수는 처음 1원짜리 동전만으로 1~10원을 구성할 때 경우의수로 채웠기 때문에 현재 dp[5]에 저장되어있습니다.

다음으로 2원을 1개 사용해서 만드는 경우의 수입니다. 그 경우의수는 현재 2원으로 갱신한 dp[3]에 저장되어 있습니다.

즉 dp[5] += dp[3]이 됩니다. dp[3] 또한 dp[3] += dp[1]로 만들어 졌기 때문에, (2,2,1)의 경우의 수를 설명 가능해집니다.

 

그러므로 일반화 된 점화식은 dp[n] += dp[n - k] (n은 현재 만들고자 하는 원, k는 현재 사용하는 동전의 가치) 로 정의됩니다.

 

다음은 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int dp[10001];
 
int main() {
 
    int n, k;
    cin >> n >> k;
 
    int coin[n];
    for(int i = 0; i < n; i++)
        cin >> coin[i];
 
    dp[0] = 1;        //0원을 만드는 경우의 수는 아무것도 안쓰는 경우의 수 = 공집합. 그러므로 1
    for(int i = 0; i < n; i++) {
        for(int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }
 
    cout << dp[k];
 
    return 0;
}

다음은 Python 코드입니다.

 

n,k = map(int, input().split())
 
coin = [] * n
dp = [0] * 10001
 
for i in range(n) :
    coin[i] = int(input())
 
dp[0] = 1
 
for i in range(n) :
    for j in range(coin[i], k + 1) :
        dp[j] += dp[j - coin[i]]
 
print(dp[k]) 

문제에서 그리디 알고리즘이 아닌 DP 방식으로 풀어야 하는 것을 빨리 찾는것이 중요하다고 생각되며, 점화식을 떠올리는데 어려웠던거 같습니다. 점화식을 보고도 이해하기 어려워서 또 여러번 풀어보는 것이 중요할것 같은 문제였습니다.

 

다음 포스트에서도 다른 백준 알고리즘으로 포스트하도록 하겠습니다. 감사합니다.