[BOJ 1943] 동전 분배

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

1943번: 동전 분배

Tag : knapsack dp

 

문제 요약

동전의 가격과 개수가 주어질 때 이를 정확히 반으로 분배할 수 있는지를 물어보는 문제다.

 

풀이

N * 동전의 합 = 100 * 100000 = \(10^7\) 이라 냅색을 돌릴 생각을 해봐야한다. 

평범한 배낭 2 처럼 개수를 ( \(2 ^ n - 1\) + a ) 형태로 저장한 후 냅색을 하면 

맞은 사람 1등에 올라갈 수 있겠다는 생각에 싱글벙글 했으나... 많은 사람들이 같은 생각을 했었고 결국 어림도 없었다. 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, sum = 0;
int dp[2][50505];
vector<int> a;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    while(cin >> n){
        sum = 0; memset(dp, 0, sizeof dp); a.clear();
        for(int i=0; i<n; i++){
            int x, y, sz = 1; cin >> x >> y; sum += x * y;
            for(int j=1; j*2-1<=y; j*=2, y-=j) a.push_back(j * x);
            for(int j=1; j<=y; j*=2) if(y & j) a.push_back(j * x);
        }
        dp[0][0]=1;
        for(int i=0; i<a.size(); i++){
            int t = i % 2;
            int x = a[i];
            for(int j=0; j<=50000; j++){
                if(dp[t][j] == 0) continue;
                dp[t ^ 1][j] = 1;
                if(j + x <= 50000) dp[t ^ 1][j + x] = 1;
            }
        }
        if(sum % 2 == 0 and dp[a.size() % 2][sum / 2]) cout << 1 << endl;
        else cout << 0 << endl;
    }
}