yukicoder contest 4(No.4)解説

No.4 おもりと天秤

おもりが釣り合う条件は、左右の重さが一致する(おもりの重さの合計の半分が左右にある)ことです。
おもりの重さは整数であるため、重さの合計が奇数である場合はoutです。
偶数である場合は、重さの合計の半分が作れるかを確認すればOKです。
作れるかどうかはDPで確認していきます。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    cin>>N;
    int W[N];
    int sum=0;

    for(int i=0;i<N;i++){
        cin>>W[i];
        sum+=W[i];
    }

    if(sum%2==1) cout<<"impossible"<<endl;
    else{
        int dp[10001]={0};
        dp[0]=1;
        for(int i=0;i<N;i++){
            for(int j=10000;j>=0;j--){
                if(dp[j]==1){
                    dp[j+W[i]]=1;
                }
            }
        }
        if(dp[sum/2]==1) cout<<"possible"<<endl;
        else cout<<"impossible"<<endl;
    }
}