1943 - 동전 분배

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

1943번: 동전 분배

과정

1. 입력을 받으면서 가능한 코인의 경우를 true로 바꿔줍니다.
2. coins를 모두 돌며 sum/2부터 역순으로 진행합니다.
3. 이전 idx를 기준으로 탐색을 진행하기 때문에 탑다운 방식으로 진행합니다.
4. 정답 이하인 경우만 진행하면 됩니다.

코드

#include<iostream>
#include<vector>

using namespace std;

vector<pair<int, int> > coins;
bool dp[100001];
int N;
int sum;

void input(){
    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;

        for(int i=1;i<=coins[i].second;++i)
            dp[i*coins[i].first] = true;
    }
}

void solution(){
    dp[0] = true;

    if(sum % 2 == 1){
        cout<<0<<'\n';
        return ;
    }

    for(int i=0;i<coins.size();++i){
        int value = coins[i].first;
        int nums = coins[i].second;

        for(int j=sum/2;j>=value;--j){
            if(dp[j-value]){
                for(int k=0;k<nums;++k){
                    if(j + value * k <= sum/2)
                        dp[j + value * k ] = true;
                    else 
                        break;
                }
            }
        }
    }

    cout<<dp[sum/2]<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T = 3;
    while(T--){
        sum = 0;
        coins.clear();
        fill(&dp[0], &dp[100001], false);
        input();
        solution();
    }

    return 0;
}