백준 1943번 동전 분배 - C++ 풀이

---

 

1. 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다.
2. dp(idx, price): [idx...]번 동전들로 price원을 만들 수 있는가
3. dp(idx, price) = max(dp(idx+1, price - coin*cnt)) (0 ≤ cnt ≤ idx번 동전개수)

1. 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다.

 만약 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다. 짝수인 경우에는 sum/2를 만들 수 있는지 확인해보면 된다.

 

1. dp(idx, price): [idx...]번 동전들로 price원을 만들 수 있는가

 dp(idx, price)를 위와 같이 정의하자. 우리가 최종적으로 구하려는 값은 dp(0, sum/2)이다. (이때 sum은 주어진 동전들의 금액 합) 기저사례는 더이상 고려할 동전이 없을 때, 즉 idx = N인 경우가 된다.

 

2. dp(idx, price) = max(dp(idx+1, price - coin*cnt)) (0 ≤ cnt ≤ idx번 동전개수)

 idx번 동전을 0개, 1개, ..., 전부 다 쓰는 경우까지 고려하여 가능한 경우가 있는지 탐색해준다. 이번 동전을 cnt개 쓰는 경우 이제 남은 동전들([idx+1...]번 동전들)로 price - coin*cnt 원을 만들어야 한다.

 

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
const int MAX_N = 101;
const int MAX_PRICE = 100'001;

int N;
vector<pii> coins;
int cache[MAX_N][MAX_PRICE];

// dp(idx, price): [idx...]번 동전들로 price원을 만들 수 있는가
int dp(int idx, int price) {
    if (price < 0) return 0;
    if (idx == N) return price == 0;
    
    int& ret = cache[idx][price];
    if (ret != -1) return ret;
    
    ret = 0;
    for (int i=0; i<=coins[idx].second; i++) {
        ret = max(ret, dp(idx+1, price - coins[idx].first*i));
    }
    
    return ret;
}

int main() {
    for (int t=0; t<3; t++) {
        int sum = 0, ans;
        
        cin >> N;
        coins.resize(N);
        for (int i=0; i<N; i++) {
            cin >> coins[i].first >> coins[i].second;
            sum += coins[i].first * coins[i].second;
        }
        
        
        if (sum % 2) {
            ans = 0;
        } else {
            memset(cache, -1, sizeof(cache));
            ans = dp(0, sum/2);
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}