[백준] 2293 - 동전 1

문제링크

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

문제

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

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

입력

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

출력

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

조건

• 시간 제한 : 0.5s

• 메모리 제한 : 4MB

---

해설

https://sihyungyou.github.io/baekjoon-2293/ 를 참고하였습니다! ㅠㅠㅠ

K=8일때 동전의 값들이 1/2/5라고 해보자.

1로 만들 수 있는 경우의 수
     1 2 3 4 5 6 7 8
dp : 1 1 1 1 1 1 1 1

1, 2로 만들 수 있는 경우의 수
     1 2 3 4 5 6 7 8
dp : 1 2 2 3 3 4 4 5

1, 2, 5로 만들 수 있는 경우의 수 
     1 2 3 4 5 6 7 8
dp : 1 2 2 3 4 5 6 7

위 값들을 만드는 데에는 다음의 식을 따른다. dp[i] = dp[i] + dp[i-n] 1, 2, 5를 이용해 7을 만드는 경우를 가정해보면, 7을 만드는 경우의 수 = 1, 2를 이용해 7을 만드는 경우의 수 + 5를 추가하여 7을 만드는 경우의 수 ( = 2를 만드는 경우의 수 )와 같다. 따라서, 5를 추가한다면 dp[7] 의 값에 dp[7] + dp[7-5]이 대입된다.

풀이

입력받은 동전의 가치를 오름차순으로 정렬하여 작은 값부터 dp를 구할 수 있게 해주었다.

for(int i = 0; i < N; i++) {
    cin >> coin[i];
}
sort(coin.begin(), coin.end());

위에 나온 식인 dp[i] = dp[i] + dp[i-n]를 코드로 옮기면 아래와 같다.

for(int i = 0; i < N; i++) {
    for(int j = 0; j < K+1; j++) {
        if(j-coin[i] >= 0) {
            dp[j] += dp[j-coin[i]];
        }
    }
}

여기에서 1, 2, 5같은 앞에 나온 값과 상관없이 추가되는 단일 동전으로 구성된 경우의 수를 추가해주기 위해서, 현재 추가하고있는 동전의 가치와 dp의 index가 같다면 (5원을 추가하는데 5원을 구성하는 경우의 수 계산 중일 때) 동전 하나로 구성이 가능하므로 1을 추가해주는 코드를 삽입해야 한다.

for(int i = 0; i < N; i++) {
    for(int j = 0; j < K+1; j++) {
        if(j-coin[i] >= 0) {
            dp[j] += dp[j-coin[i]];
        }
        
        if(coin[i] == j) {
            dp[j] += 1;
        }
    }
}

위 반복문을 수행하고 나면 원하는 결과인 K원은 dp[K]에 저장되어있다. 이를 출력해주면 된다.

cout << dp[K];

---

코멘트

열심히 고민을 했지만, 풀이를 보고 말았다. 내가 생각했던 방식에서 한 발 만 더 나갔으면 된거였는데, 그 한 발을 움직이는게 쉽지 않았던 것 같다. 이거 쉬운 문제같은데... 벌써부터 이러면 어떻게 하냐 ㅠㅠ

고민

분명 쉬운 문제인데, 중복을 제거해야한다는 조건이 생각을 복잡하게 만들었던 것 같다. 또, top-down으로 풀어야 한다는 생각에 사로잡혀서 8 = 1+7 / 2+ 6 / 5+3 으로 계속 생각하다보니 자꾸 반복을 제거하지 못해서 꼬였던 것 같다. bottom-up으로 푸는 방법에 대해서도 계속 고려를 해보자.

---

코드

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int N, K;
    cin >> N >> K;
    
    vector<int> coin(N);
    vector<int> dp(K+1, 0);
    
    for(int i = 0; i < N; i++) {
        cin >> coin[i];
    }
    sort(coin.begin(), coin.end());
       
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < K+1; j++) {
            if(j-coin[i] >= 0) {
                dp[j] += dp[j-coin[i]];
            }
            
            if(coin[i] == j) {
                dp[j] += 1;
            }
        }
    }
    
    cout << dp[K];
    return 0;
}

Uploaded by Notion2Tistory v1.1.0