제21대 국회의원 선거
알고리즘 구분 : 구현
문제
정당들의 지역구 의석 수와 비례대표 득표 결과가 각각 주어질 때, 각 정당이 21대 국회의원 선거 결과에 따라 얻게 되는 총 의석 수를 각각 계산해 보자. 의원정수는 300명이며 지역구국회의원이 253명, 비례대표국회의원이 47명이다.
비례대표 의석은 비례대표국회의원선거 유효투표총수의 3% 이상을 득표했거나 지역구국회의원선거에서 5석 이상의 의석을 차지한 정당에만 배분된다(봉쇄조항). 비례대표 의석을 배분받는 정당을 의석할당정당이라 한다. 제21대 국회의원 선거에 한해, 비례대표 의석 배분 방식은 다음과 같다.
입력
첫째 줄에는 선거에 후보를 낸 정당의 수 P와 총 투표자 수 V가 주어진다. (1 <= P <= 50), (1 <= V <= 10^9)
다음 P개의 줄에는 각 정당의 정당명과 지역구 의석 수, 비례대표국회의원선거 득표수가 주어진다. 정당명은 최대 50글자의 알파벳 소문자와 언더스코어(_)로 이루어져 있으며, 중복되지 않는다.
지역구 의석 수의 합은 253석을 넘지 않으며 비례대표국회의원선거 득표수의 합은 V를 넘지 않는다.
출력
정당별로 21대 국회에서 얻은 의석 수를 의석 수를 기준으로 내림차순으로 정렬해, 정당명과 함께 출력한다. 의석 수가 같을 경우 정당명이 사전순으로 앞서는 정당을 먼저 출력한다.
예제 입력 1
5 24430476
redshift 105 7960272
deobureo_minkyu_party 110 6069744
i_might_be_accepted 25 6355572
justice_hui 2 1719891
god_fan 0 626853
예제 출력 1
deobureo_minkyu_party 115
redshift 111
i_might_be_accepted 52
justice_hui 11
god_fan 0
이 선거에서 정당은 5곳, 투표한 유권자는 24,430,476명이다. 이를 바탕으로 계산해 보면 다음과 같다.
비례득표율은 무효표(1,698,144표)를 제외하고 계산되었다. god_fan 정당은 득표율이 3% 미만이고 지역구 의석도 5석 미만이므로 비례대표의석을 받지 못한다.
(1단계) 30석에 대해 전국단위 준연동(연동비율 50%) 방식으로 각 정당별 연동배분의석수 산정
(2-2단계) 각 정당별 연동배분의석수의 합계 > 30석 ☞ 각 정당별 연동배분의석수비율대로 배분
(3단계) 17석에 대해 기존 의석배분방식(병립형) 적용 배분
최종 의석 수
노트
2020년 1월 14일 시행된 공직선거법(법률 제16864호)을 기준으로 한다. 다만, 아래의 예외를 적용한다.
의석을 소수점 이하의 수가 큰 순서대로 배분하는 상황에서, 소수점 이하의 수가 완전히 같다면 기호가 더 작은 정당에 먼저 배분한다. (이런 경우 선거법에서는 추첨에 따르도록 되어 있다.)
적어도 한 정당 이상은
(s_i^\prime>0)임이 보장된다.
문제 풀이
문제에 주어진 양식에 맞게 구현을 진행하면 되는 문제다. 단, 조심해야할 것은 예제와 동일하게 답을 체크하면서 구현을 하다가, 문제에서 제한하지 않은 조건마저 스스로 제한하는 어리석은 생각은 조심해야할 것 같다. 나는 예제 출력을 비교하면서 문제를 풀다보니, 문제에 존재하지도 않는 조건인 소숫점 네번째 자리에서 반올림을 계속 진행하고 있었고, 해당 문제로 인해 70%에서 "틀렸습니다" 판정을 받았다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int p, v, rv, n, r;
struct node {
string name;
int ri, vote, total;
double rate, prop_rate, p1, p2, p3, p2_rate, p3_rate;
bool prop_able;
};
vector<node> party;
bool compare1(const pair<int, double> &a, const pair<int, double> &b); // 소수점 내림차순 정렬
bool compare2(const node &a, const node &b); // 전체 의석 수 내림차순 정렬
void zero(); // 득표율, 비례득표율 계산
void first(); // 1단계
void second(); // 2단계
void third(); // 3단계
void solve(); // Output 출력
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> p >> v;
rv = v;
for(int i = 0; i < p; i++) {
node temp;
cin >> temp.name >> temp.ri >> temp.vote;
party.push_back(temp);
rv -= temp.vote;
}
rv = v - rv; //유효표
zero();
first();
second();
third();
solve();
return 0;
}
bool compare1(const pair<int, double> &a, const pair<int, double> &b) {
return a.second > b.second;
}
bool compare2(const node &a, const node &b) {
if(a.total == b.total) {
return a.name < b.name;
}
else {
return a.total > b.total;
}
}
void zero() {
// 득표율 계산 + 비례대표의석 가질 수 있는지 계산 + 비례득표율용 유효 투표 수 계산
for(int i = 0; i < p; i++) {
party[i].rate = (1.0 * party[i].vote) / rv;
//party[i].rate = round(party[i].rate * 10000) / 10000;
if(party[i].ri >= 5 || party[i].rate >= 0.03) {
party[i].prop_able = true;
}
else {
party[i].prop_able = false;
rv -= party[i].vote;
}
}
// 비례득표율 계산
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].prop_rate = (1.0 * party[i].vote) / rv;
//party[i].prop_rate = round(party[i].prop_rate * 10000) / 10000;
}
}
}
void first() {
n = 300;
r = 253;
// 1단계 변수 R 계산
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
r -= party[i].ri;
}
}
// 30석에 대한 각 정당별 연동배분의석수 산정
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].p1 = ((n -r) * (1.0 * party[i].prop_rate) - party[i].ri) / 2;
if(party[i].p1 < 1) {
party[i].p1 = 0;
}
else {
party[i].p1 = round(party[i].p1);
}
}
}
}
void second() {
int sum = 0; // 정당별 연동배분의석수 합계 구하는 변수
int nSum = 0; // 정다별 연동배분의석수가 30석이 되도록 하는 변수
vector<pair<int, double>> v;
// 연동 배분 의석 수 합 구하기
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
sum += party[i].p1;
}
}
if(sum == 30) {
for(int i = 0; i < p; i++ ) {
party[i].p2 = party[i].p1;
}
return;
}
else if(sum < 30) {
// 2-1단계 구현
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].p2_rate = party[i].p1 + (30 - sum) * (1.0 * party[i].prop_rate);
party[i].p2 = floor(party[i].p2_rate);
party[i].p2_rate -= party[i].p2;
nSum += party[i].p2;
v.push_back({i, party[i].p2_rate});
}
}
sort(v.begin(), v.end(), compare1);
for(int i = 0; i < v.size(); i++) {
if(nSum >= 30) {
break;
}
party[v[i].first].p2++;
nSum++;
}
}
else if(sum > 30) {
// 2-2단계 구현
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].p2_rate = 30 * (1.0 * party[i].p1) / sum;
party[i].p2 = floor(party[i].p2_rate);
party[i].p2_rate -= party[i].p2;
nSum += party[i].p2;
v.push_back({i, party[i].p2_rate});
}
}
sort(v.begin(), v.end(), compare1);
for(int i = 0; i < v.size(); i++) {
if(nSum >= 30) {
break;
}
party[v[i].first].p2++;
nSum++;
}
}
}
void third() {
int sum = 0;
vector<pair<int, double>> v;
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].p3_rate = 17 * (1.0 * party[i].prop_rate);
party[i].p3 = floor(party[i].p3_rate);
party[i].p3_rate -= party[i].p3;
sum += party[i].p3;
v.push_back({i, party[i].p3_rate});
}
}
sort(v.begin(), v.end(), compare1);
for(int i = 0; i < v.size(); i++) {
if(sum >= 17) {
break;
}
party[v[i].first].p3++;
sum++;
}
}
void solve() {
for(int i = 0; i < p; i++) {
if(party[i].prop_able) {
party[i].total = party[i].ri + party[i].p2 + party[i].p3;
}
else {
party[i].total = party[i].ri;
}
}
sort(party.begin(), party.end(), compare2);
for(int i = 0; i < p; i++) {
cout << party[i].name << " " << party[i].total << endl;
}
}- 문제 출처 : https://www.acmicpc.net/problem/18891
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
