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

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

2293번: 동전 1

 

정답률이 높아서 좀 당황했던 문제다. 다들 천잰가...?

 

Dp 문제다. 점화식만 잘 세우면 되는데 항상 이게 어렵다. 우선 점화식부터 알아보자. 

 

dp[make] = dp[make] + dp[make - use]

dp[i] : 동전 i를 만드는 모든 경우의 수
dp[0] = 1 은 고정

 

이 점화식을 가지고 고민을 해보자. 점화식의 의미를 이해하는 것이 핵심이다. 아래 예시를 보면 이해하는 데 도움이 될 것이다. 

 

5원짜리 동전으로 7원을 만드는 경우를 생각해 보자. 1,2,3원은 이미 썼고, 5원은 처음 쓴다고 가정한다. 또한 1,2,3원으로 5원을 만드는 모든 경우의 수와 7원을 만드는 모든 경우의 수는 각각 dp[5], dp[7]에 저장되어 있다고 가정한다. 

dp[7] 에는 1,2,3원 동전으로만 사용한 경우의 수가 저장되어 있다. 5원이라는 새로운 녀석이 등장했으니깐 dp[7]에 새로 더해줘야 하는 값은 '5원을 사용하는 경우의 수'가 된다. 우리는 '5원을 사용하는 경우의 수'를 dp[2] 값으로 아주 쉽게 구할 수 있다. 간단한 퀴즈를 하나 내 보겠다. 

2 + 5 = ?

정답은 당연히 7이다. 퀴즈 하나 더.

2를 만드는 모든 경우의 수 = 동전 5를 사용하여 7을 만드는 새로운 경우의 수

이해가 되는가? 이해가 안 된다면 곰곰히 생각해 보기를 바란다. 2 + 5 = 7 이기 때문에 '새로운 동전 5를 사용해서 7을 만드는 경우의 수'는 '2를 만드는 모든 경우의 수'와 동일하다. 왜냐하면 2를 만드는 모든 경우의 수에 동전 5만 추가하면 되기 때문이다. 

 

 

위 예시를 이해했다면 점화식을 이해한 것이나 다름없다. 이제 dp[0]의 값은 왜 1로 고정되는지 생각해보자. 아주 간단한 예시를 들어 보겠다. 사용 가능한 동전이 4원 뿐이고, K = 12라고 가정해보자. 초기 dp[4]의 값은 0이다. 당연하다. 그러면 이제 4원을 사용해서 4원을 만드는 경우의 수를 생각해 보자. 점화식에 따르면 아래와 같다.

 

dp[4] = dp[4] + dp[4 - 4]

 

dp[0]의 값이 0이라면 위 식에서 dp[4]의 갱신값 또한 0이 된다. 즉, 아무런 변화가 없다. dp[4]의 값은 dp[8]을 구할때 쓰이고, dp[8]의 값은 dp[12]의 값을 구할때 쓰인다. 식을 정리하면 아래와 같다.

 

dp[4] = dp[4] + dp[0]
dp[8] = dp[8] + dp[4]
dp[12] = dp[12] + dp[8]

 

뒤에 갱신되는 모든 값의 시작은 dp[0]이다. 그리고 dp[0]의 값이 1이 아닌 다른 값이 될 수 없는 이유는 dp[0]은 동전 k로 동전 k를 만드는 경우이기 때문이다. 즉, 자기 자신으로 자기 자신을 만드는 경우는 항상 한 가지라서 dp[0]의 값 또한 항상 1이 되는 것이다. 

 

 

여기까지 다 이해했다면 풀이 코드를 어렵지 않게 이해할 수 있다. 

 

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

int dp[10001];
int N, K, tmp, use;

int main(){
    vector<int> coins;
    dp[0] = 1;
    
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        coins.push_back(tmp);
    }
    
    sort(coins.begin(), coins.end());
    
    // dp[make] = dp[make] + dp[make - use]
    for(int i = 0; i < N; i++){
        use = coins[i];
        for(int make = 0; make <= K; make++){
            if(make - use >= 0)
                dp[make] += dp[make - use];
        }
    }
    
    cout << dp[K] << endl;
    
    
    return 0;
}