백준 2293 동전 1

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

2293번: 동전 1

다이나믹 프로그래밍의 필수적인 문제이다.

 

예제를 보면 3가지의 동전으로 10을 만들어야 한다. 문제를 풀 때, 머릿속으로 골똘히 생각해 보는 것도 중요하지만, 빈 종이에 케이스를 한번 어느 정도 쭈욱 써보는 것도 큰 도움이 된다. 쓰고 나면 경향성이나 패턴을 읽어낼 수 있는 경우가 있기 때문이다.

10을 만들기 위해서는

•      1 1 1 1 1 1 1 1 1 1
•      1 1 1 1 1 1 1 1 2
•      1 1 1 1 1 1 2 2
•      1 1 1 1 2 2 2
•      1 1 2 2 2 2
•      2 2 2 2 2
•      1 1 1 1 1 5
•      1 1 1 2 5
•      1 2 2 5
•      5 5

위의 10가지 경우의 수가 가능하다. 순서가 다른 것은 같은 경우로 친다. 순서가 다른 것을 같은 경우로 치기에 동전 하나씩 골라서 전부 처리해주는 게 좋다는 발상을 할 수 있다.

즉 순회할 때 for coin in coins: (파이썬)와 같은 식으로 동전 선택이 외부 루프에 위치하도록 하는 것이다.

dp[i]를 값 i를 만드는 경우의 수라고 정의하자. 문제와 다른 예시로, 10은 9에서 1을 더해서도 만들 수 있고, 8에서 2를 더해서도 만들 수 있다. 만약에 9를 만드는 경우의 수가 5가지였고, 8을 만드는 경우의 수가 3가지였다면 (동전이 1과 2의 2가지뿐이었다고 가정한다) 10을 만드는 경우의 수는 5+3=8이 된다. 즉, dp[i+coin]+=dp[i]라고 생각할 수 있다. dp배열에서의 현재 값이 가지는 경우의 수를 위쪽에 계속 누적시켜주는 것이다.

그리고 순서가 다른 경우를 무시하기 위해 동전을 하나씩 골라서 루프를 돈다는 것이다.

 

처음에 dp는 [0, 0, 0, 0...]으로 초기화되어있다. 이렇게 하면 경우의 수가 누적되지 않는다. 모든 값이 0이기 때문에.

그래서 dp[0]=1을 넣어주면 된다. 그렇다면 dp[0+1]=dp[0+1]+dp[0]가 되고 dp[1]로 1이 누적되게 된다.

dp[5]는 dp[1+4]+=dp[4]에서 1번, dp[2+3]+=dp[3]에서 2번 (dp[3]이 2이므로), dp[0+5]+=dp[0]에서 1번으로 총 4번이 되게 된다.

이와 같은 식으로 k범위까지 누적해주면 된다.

 

<주요 내용>

다이나믹 프로그래밍

 

<코드>

파이썬

import sys
si = sys.stdin.readline

n, k = [int(e) for e in si().split()]
dp, coins = [0 for _ in range(k+1)], []
for i in range(n):coins.append(int(si()))
dp[0] = 1

for coin in coins:
    for i in range(k):
        if dp[i] and i+coin <= k:
            dp[i+coin] += dp[i]

print(dp[k])

 

C++

#include <iostream>
using namespace std;
const int big=10000+1;
int n,k,b[big];
int coins[100];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    b[0]=1;
    cin>>n>>k;
    for(int i=0;i<n;++i) cin>>coins[i];
    for(int i=0;i<n;i++){
        for(int j=coins[i];j<k+1;j++){
            int temp=b[j-coins[i]];
            if(temp) b[j]+=temp;
        }
    }
    cout<<b[k];
    return 0;
}