BOJ 1226 국회

BOJ 1226 국회

[분류 - 다이나믹 프로그래밍, 그리디]

 

[풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다.

 

$$a_i=의석수$$
$$total=\sum_{i=1}^{n} a_i$$
$$ half=\lfloor{total/2}\rfloor $$

  [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다.

 

  [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가 될 수 있을텐데, 구성된 당 중 하나를 빼면 반드시 절반 이하가 되기 위해서는 half로 구성한 당 모두가 반드시 ci보다 크거나 같아야만 조건을 만족시킬 수 있다.

 

  [다이나믹] 나머지 부분은 다이나믹 부분으로 정렬된 당에 대해 half부터 0까지 순회하면서 어느 부분에서 최대가 될 수 있는지, 어느 당을 사용했는지를 같이 저장해서 나중에 최대값 좌석수에 대해 거꾸로 추적해나가면 된다.

 

  (참고) 다이나믹 부분은 주어진 동전으로 화폐를 구성하는 경우의 수를 구하는 문제와 매우 흡사하다

 

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 301, MAX_S = 1e5 + 1, HEAD = 1e9;
int main() {
    int N, trace[MAX_S] = { HEAD }, i, j, tot = 0, half, maxi = -1, C[MAX_N];
    pair<int, int> c[MAX_N];
    vector<int> ans;
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
        scanf("%d", &C[i]);
        c[i].first = C[i];
        c[i].second = i;
        tot += c[i].first;
    }
    c[0].second = HEAD;
    sort(c + 1, c + N + 1);
    half = tot / 2;
    for (i = N; i >= 1; i--) {
        for (j = half; j >= 0; j--) if (trace[j] && !trace[j + c[i].first]) {
            trace[j + c[i].first] = c[i].second;
            if (maxi < j + c[i].first)
                maxi = j + c[i].first;
        }
    }
    while (1) {
        i = trace[maxi];
        if (i == HEAD)
            break;
        maxi -= C[i];
        ans.push_back(i);
    }
    printf("%d\n", ans.size());
    for (int& a : ans) printf("%d ", a);
    return 0;
}