[백준 1226] 국회 (C#, C++) - soo:bak

문제 링크

1226번 - 국회

설명

여러 정당이 연합하여 과반 의석을 확보하되, 연합에서 어떤 정당 하나라도 빠지면 과반을 잃게 되는 깔끔한 연합을 찾는 문제입니다. 가능한 깔끔한 연합 중 의석 합이 최대인 것을 구합니다.

접근법

먼저 깔끔한 연합의 조건을 정리합니다. 연합의 의석 합을 S, 전체 의석의 절반을 H라고 하면, 연합이 과반을 가지려면 S가 H보다 커야 합니다. 또한 어떤 정당의 의석이 s일 때, 그 정당을 빼면 과반을 잃어야 하므로 S - s가 H 이하여야 합니다. 이를 정리하면 s가 S - H 이상이어야 합니다.

즉, 깔끔한 연합에 포함된 모든 정당의 의석은 S - H 이상이어야 합니다. S - H 값이 정해지면 연합에 포함될 수 있는 정당은 의석이 그 값 이상인 정당들뿐입니다. 또한 연합의 목표 의석 합은 H에 그 값을 더한 것으로 정확히 결정됩니다.

최대 의석 합을 찾으려면 S - H 값이 클수록 유리합니다. 이 값이 크면 목표 의석 합도 커지기 때문입니다. 따라서 이 값을 가장 큰 의석부터 1까지 줄여가며 확인합니다. 각 값에서 해당 조건을 만족하는 정당들만 사용하여 목표 합을 만들 수 있는지 검사합니다.

이를 위해 부분합 동적 프로그래밍을 사용합니다. 정당을 의석 내림차순으로 정렬해두고, S - H 값을 줄여갈 때마다 새로 조건을 만족하게 된 정당들을 하나씩 추가합니다. 정당을 추가할 때마다 만들 수 있는 부분합들을 갱신합니다.

목표 합을 만들 수 있게 되는 순간, 그것이 최대 의석 합을 가지는 깔끔한 연합입니다. 어떤 정당들로 구성되었는지 복원하기 위해 각 부분합이 어떤 정당을 추가해서 만들어졌는지 기록해둡니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  struct Party {
    public int seat, id;
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var parts = Console.ReadLine()!.Split();
    var arr = new List<Party>(n);
    var total = 0;
    var maxSeat = 0;
    for (var i = 0; i < n; i++) {
      var s = int.Parse(parts[i]);
      arr.Add(new Party { seat = s, id = i + 1 });
      total += s;
      if (s > maxSeat) maxSeat = s;
    }
    var half = total / 2;
    if (total == 0) { Console.WriteLine(0); Console.WriteLine(); return; }

    arr.Sort((a, b) => b.seat.CompareTo(a.seat));

    var dp = new bool[total + 1];
    var prevSum = new int[total + 1];
    var prevId = new int[total + 1];
    Array.Fill(prevSum, -1);
    Array.Fill(prevId, -1);
    dp[0] = true;

    var idx = 0;
    List<int> answer = null;

    for (var req = maxSeat; req >= 1 && answer == null; req--) {
      while (idx < n && arr[idx].seat >= req) {
        var s = arr[idx].seat;
        var id = arr[idx].id;
        for (var sum = total - s; sum >= 0; sum--) {
          if (dp[sum] && !dp[sum + s]) {
            dp[sum + s] = true;
            prevSum[sum + s] = sum;
            prevId[sum + s] = id;
          }
        }
        idx++;
      }

      var target = half + req;
      if (target <= total && dp[target]) {
        var list = new List<int>();
        var cur = target;
        while (cur > 0) {
          list.Add(prevId[cur]);
          cur = prevSum[cur];
        }
        list.Sort();
        answer = list;
      }
    }

    if (answer == null) {
      Console.WriteLine(0);
      Console.WriteLine();
    } else {
      Console.WriteLine(answer.Count);
      Console.WriteLine(string.Join(" ", answer));
    }
  }
}

C++

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

typedef vector<int> vi;
typedef vector<char> vc;

struct Party {
  int seat, id;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; if (!(cin >> n)) return 0;
  vector<Party> p(n);
  int total = 0, maxSeat = 0;
  for (int i = 0; i < n; i++) {
    cin >> p[i].seat;
    p[i].id = i + 1;
    total += p[i].seat;
    maxSeat = max(maxSeat, p[i].seat);
  }
  int half = total / 2;
  if (total == 0) { cout << 0 << "\n\n"; return 0; }

  sort(p.begin(), p.end(), [](const Party& a, const Party& b) {
    return a.seat > b.seat;
  });

  vc dp(total + 1, false);
  vi prevSum(total + 1, -1), prevId(total + 1, -1);
  dp[0] = true;

  int idx = 0;
  vi answer;

  for (int req = maxSeat; req >= 1 && answer.empty(); req--) {
    while (idx < n && p[idx].seat >= req) {
      int s = p[idx].seat, id = p[idx].id;
      for (int sum = total - s; sum >= 0; sum--) {
        if (dp[sum] && !dp[sum + s]) {
          dp[sum + s] = true;
          prevSum[sum + s] = sum;
          prevId[sum + s] = id;
        }
      }
      idx++;
    }

    int target = half + req;
    if (target <= total && dp[target]) {
      int cur = target;
      while (cur > 0) {
        answer.push_back(prevId[cur]);
        cur = prevSum[cur];
      }
      sort(answer.begin(), answer.end());
    }
  }

  if (answer.empty()) {
    cout << 0 << "\n\n";
  } else {
    cout << answer.size() << "\n";
    for (size_t i = 0; i < answer.size(); i++)
      cout << answer[i] << (i + 1 == answer.size() ? '\n' : ' ');
  }

  return 0;
}