[BOJ 1226] 국회

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

1226번: 국회

 

- 문제 요약

 

국회에는 당이 N개 있고, 각각의 당은 확보한 의석이 있다.

이번에 당끼리 연합을 맺기로 했다. 연합이 유효하려면, 연합에 속한 당의 의석의 합이 전체 의석의 반을 넘어야 한다.

유효한 연합에서 소속된 당 하나를 제거했을 때, 여전히 유효한 연합이라면, 그 연합을 깔끔하지 못한 연합이라고 한다. 유효한 연합 중에서 깔끔하지 못한 연합을 제외한 것을 깔끔한 연합이라고 한다. 깔끔한 연합 중, 포함하는 의석의 수가 가장 많은 것을 찾는 프로그램을 작성하시오.

(모든 당의 의석 수의 합은 100,000을 넘지 않는다.)

 

 

- 알고리즘 정리

 

포함하는 의석의 수가 가장 큰 깔끔한 연합을 찾는 것보다, 크기가 X(임의의 수)인 깔끔한 연합을 찾는 게 더 편할 것 같아서 이 방법으로 문제를 해결했습니다.

연합 내에서 가장 작은 당의 크기가 클 수록 깔끔한 연합일 확률이 높아집니다. 이 부분을 활용해서 백트래킹과 DP로 문제를 해결해 주면 됩니다. 

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
ll n,sum,result,a[MAX],b[MAX],c[MAX],co;
pair<ll,ll>arr[1001];
vector<ll>v;

bool cmp(pair<ll,ll>a,pair<ll,ll>b){
	return a.first<b.first;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i].first;
		arr[i].second=i;
		sum+=arr[i].first;
	}
	sort(arr+1,arr+1+n,cmp);
	for(int i=n;i>=1;i--){
		for(int j=sum;j>=0;j--){
			if(arr[i].first+j<=sum&&(j==0||a[j]!=0)&&a[j+arr[i].first]==0){
				a[j+arr[i].first]=i;
                b[j+arr[i].first]=arr[i].second;
                c[j+arr[i].first]=j;
			}
		}
	}
	for(int i=sum;i>=1;i--){
		if(i-arr[a[i]].first<=sum/2){
			co=i;
			break;
		}
	}
	while(co){
		v.push_back(b[co]);
        result++;
        co=c[co];
	}
	cout<<result<<'\n';
	for(auto i:v){
		cout<<i<<" ";
	}
}

코드 제출 결과