[C++/BOJ] 2293 : 동전 1

 

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

---

 

백준 골드 5 문제!

백트래킹이나 완탐 문제일 줄 알았는데 알고보니 dp였다....

 

 

0원인 경우의 수는 1이다. dp[0] = 1;

 

1원이 가능한 경우의 수는 1원짜리 동전이 있어야 성립한다. 있다고 가정하면 dp[1] = 1;

 

2원이 가능한 경우의 수는 2원짜리 동전이 있다면 추가된다.

dp[2] = 2 = 'dp[1]+1원짜리 동전 더하는 경우' and '2원짜리 동전 하나' ;

 

2원짜리 동전이 없고 1원짜리만 있다면 dp[2] = 1 = 'dp[1]+1원짜리 동전 더하는 경우'

 

쭉 생각해보면 결국 dp[ i ] = 'dp[ i - 코인 단위 ] + 그 코인을 더하는 경우' 이다.

 

여기서는 코인이 여러개이므로 위 과정을 반복하여 누적시키면 된다.

 

 

c++ 풀이

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int k;
    int coin[102] = {0,};
    int dp[10002] = {0,};
    cin >> n >> k;
    for (int i = 0; i < n; ++i){
        cin >> coin[i];
    }
    dp[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;
}