백준 1943, 동전 분배

개요

문제 링크
골드 3, DP
전체 합의 절반을 배낭문제로 구성할 수 있는지 확인하기

---

접근

1. 구성 여/부만 판단하면 되므로 동전의 사용 개수에 대해 dp에 저장하지 않고 해결할 방법을 생각해야 함.
2. 배낭문제로 풀어주면 되는데, 사용할 값은 현재 값까지 오면서 남은 각각의 동전의 개수이고, 업데이트는 모든 동전마다 순회하면서 (현재값)-(동전가치)와 비교해주면 됨.
3. 이게 되는 이유? 동전의 개수가 생각보다 적음. 동전의 가치는 모두 다르므로 1부터 n까지 1개씩만 있다고 할 때 총합이 100,000이하이므로 n의 최대는 sqrt(200,000) ~= 450
   즉 (총합의 절반) * (동전종류) 까지 순회 돌면 되니까 50000×450번 안에 해결 가능
4. C언어와 달리 C++의 미친 장점, map을 사용했으나 실패, map에 저장했던 내용은 <동전의 값, 개수> 였는데 map은 아무래도 느려서 vector <동전종류,개수>로 해결해 줌.

---

Pseudo code

if (총합이 홀수)
    return 0
for (i = 1 ~ 총합 / 2)
    for (j = coin 종류)
        이전값 = i - j번째 코인가치
        if (이전값 = 양수)
            prev_coin = 이전값 코인구성
            if (구성가능[이전값] && prev_coin에 j번째 코인이 남아있다면)
                new_coin = prev_coin에서 j번째 코인을 하나 줄임
                i의 코인구성 = new_coin
                구성가능[i] = 1

---

Source code

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> coin;

int test() {
    int n;
    cin >> n;
    int s, x[n], y[n];
    coin a;
    s = 0;
    for (int i=0; i<n; i++) {
        cin >> x[i] >> y[i];
        a.push_back(y[i]);
        s += x[i]*y[i];
    }
    if (s % 2)
        return 0;

    int h = s/2;
    coin m[h+1];
    int dp[h+1];
    m[0] = a;
    dp[0] = 1;
    for (int i=1; i<=h; i++) {
        dp[i] = 0;
        for (int j=0; j<n; j++) {
            int k = i-x[j];
            if (0 <= k) {
                a = m[k];
                if (dp[k] && a[j]) {
                    a[j]--;
                    m[i] = a;
                    dp[i] = 1;
                }
            }
        }
    }
    return dp[h];
}

int main() {
    int t = 3;
    while(t--) {
        cout << test() << "\n";
    }
}