[BOJ][C++] 백준 2293번: 동전 1

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

2293번: 동전 1

 

문제

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

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

입력

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

출력

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

 

풀이

dp문제긴한데 조금 생각이 필요하다

예제에 나와있는 1,2,5원으로 10(k)원을 만드는 경우들을 생각해보자

 

1원 | 1
2원 | 11 2
3원 | 111 21
4원 | 1111 211 22
5원 | 11111 2111 221 5
6원 | 111111 21111 2211 222 51
7원 | 1111111 211111 22111 2221 511 52
8원 | 11111111 2111111 221111 22211 5111 521 2222
9원 | 111111111 21111111 2211111 222111 51111 5211 22221 522
10원 | 1111111111 211111111 22111111 2221111 511111 52111 222211 5221 22222 55

 

a. 1원으로만 만들 수 있는 경우 - 파랑

b. 1원과 2원으로 만들 수 있는 경우 - 검정

c. 1원과 2원과 5원으로 만들 수 있는 경우 - 빨강

 

세 경우를 따로 생각해줘야 중복을 방지할 수 있다

a b c의 경우를 순차적으로 구하자

 

dp[i] = i원을 만들 수 있는 경우의 수

a ) 1 1 1 1 1 1 1 1 1 1 
b ) 1 2 2 3 3 4 4 5 5 6 
c ) 1 2 2 3 4 5 6 7 8 10 

 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,k;
    cin >> n >> k;
    vector<int>v;
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        if(tmp>k) continue;
        v.push_back(tmp);
    }
    n = v.size();
    sort(v.begin(), v.end());
    
    vector<long long>dp(k+1, 0);
    for(int i=0; i<n; i++) {
        int coin = v[i];
        dp[coin]++;
        for(int j=coin+1; j<=k; j++) {
            dp[j] += dp[j-coin];
        }
    }
    
    cout << dp[k];
 
}​

 

 

 

시행착오 - 메모리초과

2차원 dp를 이용하여 구현한 방식 메모리 초과가 뜨더라..

 

1원 | 1
2원 | 11 2
3원 | 111 21
4원 | 1111 211 22
5원 | 11111 2111 221 5
6원 | 111111 21111 2211 222 51
7원 | 1111111 211111 22111 2221 511 52
8원 | 11111111 2111111 221111 22211 5111 521 2222
9원 | 111111111 21111111 2211111 222111 51111 5211 22221 522
10원 | 1111111111 211111111 22111111 2221111 511111 52111 222211 5221 22222 55

 

1원(첫번째 동전)이 한번이라도 포함되면 검정색

1원 포함 안하고 2원(두번째 동전)이 한번이라도 포함되면 파란색

1원과 2원 포함 안하고 5원(세번째 동전)이 한번이라도 포함되면 빨강색

 

v[i] = i번째 동전의 값dp[k][i] = i번째 동전과 그 다음 동전들로만 K원을 만들 수 있는 경우의 수 로 뒀다

 

즉 예제에서는dp[k][0] = dp[k-1][0] + dp[k-2][1] + dp[k-5][2];dp[k][1] = dp[k-2][1] + dp[k-2][2];dp[k][2] = dp[k-5][2];

 

금액 1 2 3 4 5 6 7 8 9 10
검정 1 1 2 2 3 4 5 6 7 8
파랑 0 1 0 1 0 1 1 1 1 1
빨강 0 0 0 0 1 0 0 0 0 1

 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,k;
    cin >> n >> k;
    vector<int>v(n);
    vector<vector<long long>>dp(k+1, vector<long long>(n, 0));
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++) {
        if(v[i]>k) break;
        dp[v[i]][i] = 1;
    }
    
    for(int i=1; i<k+1; i++) {
        for(int j=0; j<n; j++) {
            int coin = v[j];
            if(i-coin <= 0) break;
            
            int sum = 0;
            for(int h=j; h<n; h++) {
                dp[i][j] += dp[i-coin][h];
            }
        }
    }
    
    long long ans = 0;
    for(int i=0; i<n; i++) {
        ans += dp[k][i];
    }
    cout << ans;
 
}