[백준/BOJ] 2293번 동전 1 (C++)

www.acmicpc.net/problem/2293

2293번: 동전 1

DP 유형의 문제입니다.

점화식을 도출해내기 위해서 동전의 종류가 1원, 2원, 5원이 있고 숫자 10을 만드는 경우의 수를 구한다고 했을 때 밑의 예시를 살펴보겠습니다.

 

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

 

1번부터 10번까지 dp 테이블을 만들고, 동전 1원으로 만들 수있는 경우를 살펴보면 전부 1개입니다. 그렇다면 다음으로 1원과 2원을 이용한 경우는 어떻게 되는지 살펴보겠습니다.

 

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
1	2	2	3	3	4	4	5	5	6

 

dp 테이블의 숫자 2부터 수가 변한 것을 확인할 수 있습니다. 숫자 2를 만들 수 있는 경우는 1+1, 2 총 2가지 입니다. 더 살펴보겠습니다. 숫자 3을 만드는 경우는 1+1+1, 1+2 총 2가지 입니다. 이를 통해 한가지 규칙을 찾아낼 수 있는데, 새로 갱신되는 dp[n]의 값은 이전 dp[n] 값에서 dp[n - 현재 동전의 종류 크기] 를 더한 값이라는 점입니다. 

 

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
1	2	2	3	3	4	4	5	5	6
1	2	2	3	4	5	6	7	8	10

 

1원, 2원, 5원을 이용하는 경우입니다. 이번에는 숫자 5부터 수가 변한 것을 확인할 수 있습니다. 그리고 역시나 같은 규칙을 가지고 있습니다. 따라서 위의 방법과 동일하게 모든 동전의 종류에 대해서 dp 테이블의 값을 갱신하면 됩니다. 이러한 과정을 거치므로 점화식은 다음과 같이 정의할 수 있습니다.

 

dp[n] = dp[n] + dp[n - v[i])

 

#include <iostream>
#include <vector>
using namespace std;

int dp[10001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin>>n>>k;
    vector<int> v(n + 1);
    
    for(int i = 1; i <= n; i++) {
        cin>>v[i];
    }
    
    // 초기값 설정
    dp[0] = 1;
    
    // 동전의 종류마다 k번까지 최대 경우의 수가 갱신된다.
    for(int i = 1; i <= n; i++) {
        // 동전의 종류와 같은 수부터 갱신된다. (그 이전은 그대로 유지)
        for(int j = v[i]; j <= k; j++) {
            dp[j] += dp[j - v[i]];
        }
    }

    cout<<dp[k];
}