BOJ 1226 - 국회

문제 링크 : https://www.acmicpc.net/problem/1226

문제 소개

어떤 당이 빠져도 합이 과반수가 안되는 집합을 깔끔한 연합이라고 한다. 가장 큰 크기의 깔끔한 연합을 구하여라.

문제 풀이

가장 큰 크기의 깔끔한 연합을 구하는 것이 아니라 관점을 바꾸어서 크기가 K인 깔끔한 연합이 존재하는 지에 대해서 구해도 된다. 모든 값에 대해서 다 가능성을 구해주면 된다.

일단 기본적으로 몇 개의 값의 합이 K가 되어야 한다. 합이 K가 되는 여러가지 방법중 깔끔한 연합이 될 확률이 가장 높은 것은 것은 연합내의 가장 작은 값이 커야 한다는 것이다. 가장 작은 값만 빼더라도 과반수가 안되면 깔끔한 연합이라고 할 수 있고, 그러기 위해서는 연합내 가장 작은 값이 커야한다.

따라서 N개의 숫자들을 하나씩 보면서, 동전교환 DP처럼 진행해준다. 이를 이용해 합이 K가 되는 깔끔한 연합이 있는지를 확인 할 수 있고, 동전 교환 DP과정에서 백트리킹 까지 준비해 놓으면 전제적인 문제를 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll idx,val;
};
 
bool sf(poi a,poi b){
    return a.val<b.val;
}
 
poi arr[1010];
ll dep[1010101];
ll now[1010101];
ll pre[1010101];
 
vector<ll>v;
 
int main(){
    ll i,j,k,l,m,n,sum=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&arr[i].val);
        arr[i].idx=i;
        sum+=arr[i].val;
    }
    sort(arr+1,arr+1+n,sf);
    for(i=n;i>=1;i--)
        for(j=sum;j>=0;j--)
            if(arr[i].val+j<=sum&&(j==0||dep[j]!=0)&&dep[j+arr[i].val]==0){
                dep[j+arr[i].val]=i;
                now[j+arr[i].val]=arr[i].idx;
                pre[j+arr[i].val]=j;
            }
    ll fl,ans=0;
    for(i=sum;i>=1;i--){
        if(i-arr[dep[i]].val<=sum/2){
            fl=i;
            break;
        }
    }
    while(fl){
        v.push_back(now[fl]);
        ans++;
        fl=pre[fl];
    }
 
    printf("%lld\n",ans);
    for(auto x:v)
        printf("%lld ",x);
    
}