백준 1226번, BOI 2008 4번, 국회 풀이

문제

백준 1226번

풀이

솔직히 문제 번역본이 그렇게 좋은 것 같진 않습니다.

$ N $개의 정당 중 $ K $개의 정당을 뽑아서 연합을 만들 수 있습니다. ($ A_{i} $: $ i $번째 정당의 인원수)

이 연합에 속한 정당의 인원들의 합이 전체 정당의 인원수($ \sum_{i=1}^n A_{i} $)의 절반 이상이어야 하며, 연합 중 임의의 한 정당을 뺐을 때 연합의 인원수의 합이 전체 정당의 인원수의 반 미만이 되는 것을 모두 만족해야 합니다. 위 조건을 모두 만족하는 연합 중 가장 많은 인원수를 가지는 연합을 찾는 문제입니다.

 

 

문제를 그리디로 접근하면,

정당의 인원수가 많은 것부터 보면서, 전체 정당의 인원수의 절반($ \frac{(\sum_{i=1}^n A_{i})}{2} $)을 처음으로 넘기는 연합을 구해야 합니다.

 

가령, 테스트 케이스에서 전체 정당의 인원수가 $ 10 $이니, 큰 정당들부터 보면서, 연합에 속한 정당 인원수의 합이 5 이상이 되도록 하면 됩니다.

 

정렬을 하면 $ [4, 3, 2, 1] $이 됩니다. 큰거부터 보면, $ [4, 3] $이 가능합니다. 이 경우 과반수도 넘으며, 어떠한 정당을 빼더라도 인원이 과반수보다 아래니 가능한 조합입니다. 한편, $ [4, 3, 2, 1], [4, 3, 2]... $와 같은 조합은 정당 하나를 없애면 과반수보다 많은 경우가 있어 불가능한 조합입니다.

 

이 그리디 구현은 DP로 접근하여, $ dp[i] = j$번째 정당일 때, 가능한 최적의 조합 으로 점화식을 세우면 풀 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
	cout.tie(nullptr);
	vector<pair<int, int>> l;

	int sum = 0;
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		l.emplace_back(a, i);
		sum += a;
	}

	sort(l.begin(), l.end(), greater<>());
	vector<int> dp[100001];
	int ans = 0;
	dp[0].push_back(-1);

	for (const auto &info : l) {
		for (int base = sum / 2; base >= 0; base--) {
			int after = info.first + base;
			if (!dp[base].empty() && dp[after].empty()) {
				ans = max(ans, after);
				dp[after] = dp[base];
				dp[after].push_back(info.second);
			}
		}
	}

	cout << dp[ans].size() - 1 << "\n";
	for (const auto &i : dp[ans]) if (i > 0) cout << i << " ";
}