BOJ 1943 - 동전 분배

www.acmicpc.net/problem/1943

1943번: 동전 분배

 

문제에서 요구하는 것은 정확히 절반으로 나눠서 두개로 나눌 수 있는가 없는가 이며,

이를위한 DP 1차원 배열을 만드는데 i 번째 인덱스의 의미는 i 원을 만들어 낼 수 있는지 없는지 판별한값이 들어간다

 

합이 홀수라면 어떻게 나눠도 정확히 두개로 나눠서 가질 수 없으므로, 예외처리 해주고

합이 짝수인 경우에 한해서 DP 배열을 채운다.

 

이 문제에서 가장 핵심은, 탑다운 방식으로 탐색해야 한다는것이다.

반대의 방식으로 탐색하면 1원으로 모든 DP 배열을 채울 수 있다.

1원으로 2원, 3원, 4원 .... N 원 까지 전부 만들 수도 있어서, 문제의 조건과 맞지 않는 결과가 나오게된다.

 

 

- C++

#include <algorithm>
#include <cstring>
#include <iostream>
 
using namespace std;
 
int N;
pair<int, int> coin[101]; // 동전의 가치, 동전의 갯수 
bool dp[50001]; // dp[i] => i 원을 만들어 낼 수 있는가 없는가 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    for (int tc = 0; tc < 3; ++tc) {
        int sum = 0; 
        memset(dp, false, sizeof(dp)); // 매 케이스마다 초기화필요 
        dp[0] = true; // 0 원은 당연히 true 
        
        cin >> N;
        for (int i = 0; i < N; ++i) {
            cin >> coin[i].first >> coin[i].second; 
            sum += (coin[i].first * coin[i].second);
        }
        
        if (sum % 2 == 1) { // 합이 홀수면 절반으로 분배 불가능 
            cout << "0\n";
            continue;
        }
        
        sort(coin, coin + N);
        
        for (int i = 0; i < N; ++i) {
            for (int j = sum / 2; j >= coin[i].first; --j) {
                if (dp[j - coin[i].first]) {
                    for (int k = 0; k < coin[i].second; ++k) {
                        if (j + k * coin[i].first > sum / 2) break;
                        dp[j + k * coin[i].first] = true;
                    }
                }
            }
        } 
        
        cout << dp[sum / 2] << "\n";
    }
    
    return 0;
}