[boj] 백준 2293 동전1 - 동적프로그래밍

[문제]

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

2293번: 동전 1

 

[풀이]

동적 프로그래밍 문제이다. coin 배열에 동전의 가치들을 저장해두고 dp[a] = b에 대해 a원을 만들 수 있는 경우의 수 b로 두고 접근한다. 0원을 만드는 경우의 수도 1가지이므로 dp[0] = 1로 둔다.

동전의 가치가 1, 2, 5가 있고 10을 만들 수 있는 경우의 수를 구한다고 하자. 동전 1에 대해서 1을 만들 수 있는 경우의 수는 0을 만들 수 있는 경우의 수와 같다. 0을 만들 수 있는 경우의 수에 동전 1만 추가하면 되기 때문이다. 마찬가지로 2를 만들 수 있는 경우의 수는 1을 만들 수 있는 경우의 수와 같고, 10을 만들 수 있는 경우의 수는 9를 만들 수 있는 경우의 수와 같다. 따라서 처음에는 dp[i]가 모두 1이 된다.

다음으로 2를 이용해 10을 만들 수 있는 경우의 수를 구해보자. 동전 2를 이용해 0, 1을 만들 수는 없으므로 2부터 시작한다. 2를 이용해 2를 만들 수 있는 방법은 0을 만드는 경우의 수를 더하면 된다. 0을 만드는 경우의 수에 2를 추가로 내는 것이기 때문이다. 같은 dp 배열을 사용하므로 앞서 구한 dp[2](1을 이용해 2를 만드는 경우의 수)에 그대로 더해준다. 

마찬가지로 5를 만드는 경우의 수 역시 동전 5를 이용해 0 , 1, 2, 3, 4를 만들 수 없으므로 5부터 시작한다. 0원을 만드는 경우의 수를 dp[5]에 더하면 되고, 그 후 10이 될 때까지 같은 방식으로 구한다. dp[6]에는 1을 만드는 경우의 수를 더해준다. (1을 만들 수 있는 경우의 수에 5를 추가로 내면 6이 되므로)

 

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace::std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k; //n개의 종류의 동전으로 가치의 합이 k원이 되게 하는 경우의 수
    cin >> n >> k;
    vector<int> coin(n);
    vector<int> dp(k+1);
    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];

}