18891번: 제21대 국회의원 선거
정당들의 지역구 의석 수와 비례대표 득표 결과가 각각 주어질 때, 각 정당이 21대 국회의원 선거 결과에 따라 얻게 되는 총 의석 수를 각각 계산해 보자. 의원정수는 300명이며 지역구국회의원
www.acmicpc.net
문제
정당들의 지역구 의석 수와 비례대표 득표 결과가 각각 주어질 때, 각 정당이 21대 국회의원 선거 결과에 따라 얻게 되는 총 의석 수를 각각 계산해 보자. 의원정수는 300명이며 지역구국회의원이 253명, 비례대표국회의원이 47명이다.
비례대표 의석은 비례대표국회의원선거 유효투표총수의 3% 이상을 득표했거나 지역구국회의원선거에서 5석 이상의 의석을 차지한 정당에만 배분된다(봉쇄조항). 비례대표 의석을 배분받는 정당을 의석할당정당이라 한다. 제21대 국회의원 선거에 한해, 비례대표 의석 배분 방식은 다음과 같다.
(1단계) 30석에 대해 전국단위 준연동(연동비율 50%) 방식으로 각 정당별 연동배분의석수 산정
의석할당정당이 비례대표국회의원선거에서 얻은 득표비율에 따라 산정한 의석수에서 해당 정당의 지역구국회의원 당선인 수를 뺀 후, 그 수의 50%에 이를 때까지 해당 정당에 비례대표 국회의원 의석을 먼저 배분한다.
(N: 국회의원 정수, R 의석할당정당이 아닌 정당의 지역구 당선인 수 총합 + 무소속 지역구 당선인 수, pi: 해당 정당의 비례대표국회의원선거 득표비율, ri: 해당 정당의 지역구국회의원 당선인 수)
pi는 전체 유효표에 대한 득표비율이 아니고, 의석할당정당의 득표수를 모든 의석할당정당의 득표수의 합계로 나누어 다시 산출됨에 주의한다.
결과값은 1보다 작을 경우 0이며, 이외의 경우 소수점 첫째 자리에서 반올림한다. 이렇게 계산된 정수를 연동 배분 의석 수 si′이라 한다.
si의 합이 30인 경우 이 의석 수를 47석 중 30석에 대한 해당 정당의 비례대표 의석 수(si)로 확정한다.
(2-1단계) 각 정당별 연동배분의석수의 합계 < 30석일 경우 ☞ 잔여의석에 대해 기존 의석배분방식(병립형) 적용 배분
1단계에서 배분한 의석의 합이 30석을 넘지 못하여 잔여의석이 생기면, 잔여의석은 비례대표국회의원선거의 득표비율에 따라 산정한 의석을 배분한다.
(pi: 해당 정당의 비례대표국회의원선거 득표비율)
계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 30석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 30석에 대한 조정된 비례대표 의석 수 si라 한다.
(2-2단계) 각 정당별 연동배분의석수의 합계 > 30석 ☞ 각 정당별 연동배분의석수비율대로 배분
1단계에서 배분한 의석의 합이 30석을 넘어 초과의석이 생기면, 각 정당별 연동배분의석수비율대로 다시 배분한다.
계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 30석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 30석에 대한 조정된 비례대표 의석 수 si라 한다.
(3단계) 17석에 대해 기존 의석배분방식(병립형) 적용 배분
나머지 17석에 대해 비례대표국회의원선거의 득표비율에 따라 산정한 의석을 배분한다.
(pi: 해당 정당의 비례대표국회의원선거 득표비율)
계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 17석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 17석에 대한 비례대표 의석 수 ti라 한다.
최종적으로 정당 i의 비례의석은 si+ti석이며, 지역구의석 수 ri와 합치면 해당 정당이 21대 국회에서 얻는 총 의석 수는 si+ti+ri가 된다.
입력
첫째 줄에는 선거에 후보를 낸 정당의 수 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명이다. 이를 바탕으로 계산해 보면 다음과 같다.
| i = 기호 | 정당명 | ri = 지역구 의석 | 득표율 |
| 1 | redshift | 105 | 0.3502 |
| 2 | deobureo_minkyu_party | 110 | 0.2670 |
| 3 | i_might_be_accepted | 25 | 0.2796 |
| 4 | justice_hui | 2 | 0.0757 |
| 5 | god_fan | 0 | 0.0276 |
| 0 | 무소속 | 11 |
비례득표율은 무효표(1,698,144표)를 제외하고 계산되었다. god_fan 정당은 득표율이 3% 미만이고 지역구 의석도 5석 미만이므로 비례대표의석을 받지 못한다.
(1단계) 30석에 대해 전국단위 준연동(연동비율 50%) 방식으로 각 정당별 연동배분의석수 산정
| i = 기호 | 정당명 | ri = 지역구 의석 | pi = 비례득표율 | si′ = 연동 배분 의석 |
| 1 | redshift | 105 | 0.3601 | 0 |
| 2 | deobureo_minkyu_party | 110 | 0.2746 | 0 |
| 3 | i_might_be_accepted | 25 | 0.2875 | 29 |
| 4 | justice_hui | 2 | 0.0778 | 10 |
(2-2단계) 각 정당별 연동배분의석수의 합계 > 30석 ☞ 각 정당별 연동배분의석수비율대로 배분
| i = 기호 | 정당명 | si′ = 연동 배분 의석 | si = 조정된 비례대표 의석 |
| 1 | redshift | 0 | 0 |
| 2 | deobureo_minkyu_party | 0 | 0 |
| 3 | i_might_be_accepted | 29 | 22 |
| 4 | justice_hui | 10 | 8 |
(3단계) 17석에 대해 기존 의석배분방식(병립형) 적용 배분
| i = 기호 | 정당명 | pi = 비례득표율 | ti = 연동 배분 의석 |
| 1 | redshift | 0.3601 | 6 |
| 2 | deobureo_minkyu_party | 0.2746 | 5 |
| 3 | i_might_be_accepted | 0.2875 | 5 |
| 4 | justice_hui | 0.0778 | 1 |
최종 의석 수
| i = 기호 | 정당명 | ri | si | ti | 합계의석 |
| 1 | redshift | 105 | 0 | 6 | 111 |
| 2 | deobureo_minkyu_party | 110 | 0 | 5 | 115 |
| 3 | i_might_be_accepted | 25 | 22 | 5 | 52 |
| 4 | justice_hui | 2 | 8 | 1 | 11 |
| 5 | god_fan | 0 | 0 | 0 | 0 |
| 0 | 무소속 | 11 | 0 | 0 | 11 |
노트
2020년 1월 14일 시행된 공직선거법(법률 제16864호)을 기준으로 한다. 다만, 아래의 예외를 적용한다.
- 의석을 소수점 이하의 수가 큰 순서대로 배분하는 상황에서, 소수점 이하의 수가 완전히 같다면 기호가 더 작은 정당에 먼저 배분한다. (이런 경우 선거법에서는 추첨에 따르도록 되어 있다.)
적어도 한 정당 이상은 si′>0임이 보장된다.
알고리즘 분류
- 구현
풀이
문제를 잘 읽고 주어진 조건대로 구현하면 되지만 소수점을 잘 계산하여야 한다.
그리고 비례대표국회의원을 나눌 때 30 이하인 경우, 17 이하인 경우 이렇게 if 조건문을 달아줘야 통과하는 것 같다. 본인은 처음에 그러한 조건문을 달아주지 않아서 계속 틀렸다.
코드
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005
#define LL long long
#define INF 1e9
using namespace std;
struct INFO {
int IDX;
string Name; // 정당명
int R, Vote; // 지역구 의석, 비례대표국회의원선거 득표수
double Vote_Rate; // 비례득표율
bool Flag1 = true; // 의석 할당 정당이라면 true, 아니라면 false
double P; // 비례득표율
int S_Appo = 0, S = 0, T = 0; // 연등 배분 의석, 조정된 비례대표 의석, 연등 배분 의석
int Total = 0;
};
int P, V;
int True_R = 0;
vector<INFO> Party;
int S_Appo_Sum = 0;
int True_Vote = 0; // 유효 투표 총 수
int Total_True_Vote;
void init() {
Total_True_Vote = True_Vote;
// 유효 투표 총 수의 3% 미만을 득표했거나, 지역구 국회의원 선거에서 5석 미만의 의석을 차지한 정당은 비례대표 의석을 배분받을 수 없다.
for (int i = 0; i < Party.size(); i++) {
double Rate = (double)Party[i].Vote / (double)True_Vote;
Party[i].Vote_Rate = Rate;
if ((Party[i].R < 5) && (Party[i].Vote_Rate < 0.03)) {
Party[i].Flag1 = false;
Total_True_Vote -= Party[i].Vote; // 의석 할당 정당이 아닌 정당의 득표 수를 실 득표 수에서 제외시킨다.
}
}
for (int i = 0; i < Party.size(); i++) {
// i번 기호의 정당의 비례대표 국회의원 선거 득표비율을 구한다. 즉 의석 할당 정당의 득표수를 모든 의석 할당 정당의 득표수의 합계로 나누어 다시 산출한다.
if (Party[i].Flag1) {
Party[i].P = (double)Party[i].Vote / (double)Total_True_Vote;
True_R += Party[i].R;
}
}
}
bool Comp(pair<int, double> A, pair<int, double> B) {
return (A.second > B.second);
}
void Second_Step_First() {
int Now_Total_S = 0;
vector<pair<int, double> > Vec; // (기호, 소수점 이하의 수)
for (int i = 0; i < Party.size(); i++) {
if (Party[i].Flag1) {
double Res = Party[i].S_Appo + (30 - S_Appo_Sum) * Party[i].P;
double Remain = Res - floor(Res);
Party[i].S = floor(Res);
Now_Total_S += Party[i].S;
Vec.emplace_back(make_pair(i, Remain));
}
}
if (Now_Total_S < 30) {
sort(Vec.begin(), Vec.end(), Comp);
for (int i = 0; i < Vec.size(); i++) {
int X = Vec[i].first;
Party[X].S++;
Now_Total_S++;
if (Now_Total_S == 30) {
break;
}
}
}
}
void Second_Step_Second() {
int Now_Total_S = 0;
vector<pair<int, double> > Vec; // (기호, 소수점 이하의 수)
for (int i = 0; i < Party.size(); i++) {
if (Party[i].Flag1) {
double Res = 30.0 * Party[i].S_Appo / (double)S_Appo_Sum;
double Remain = Res - floor(Res);
Party[i].S = floor(Res);
Now_Total_S += Party[i].S;
Vec.emplace_back(make_pair(i, Remain));
}
}
if (Now_Total_S < 30) {
sort(Vec.begin(), Vec.end(), Comp);
for (int i = 0; i < Vec.size(); i++) {
int X = Vec[i].first;
Party[X].S++;
Now_Total_S++;
if (Now_Total_S == 30) {
break;
}
}
}
}
void First_Step() {
for (int i = 0; i < Party.size(); i++) {
if (Party[i].Flag1) {
double Res = (((47 + True_R) * Party[i].P) - Party[i].R) / 2.0;
// 결과값은 1보다 작은 경우 0이며, 이외의 경우 소수점 첫째 자리에서 반올림한다.
if (Res < 1) {
Party[i].S_Appo = 0;
}
else {
Party[i].S_Appo = round(Res);
}
S_Appo_Sum += Party[i].S_Appo;
}
}
if (S_Appo_Sum < 30) { // 연등 배분 의석 수의 합이 30 이하인 경우 2-1단계로 진입한다.
Second_Step_First();
}
else if (S_Appo_Sum > 30) { // 연등 배분 의석 수의 합이 30 초과인 경우 2-2단계로 진입한다.
Second_Step_Second();
}
}
void Third_Step() {
int Now_Total_T = 0;
vector<pair<int, double> > Vec; // (기호, 소수점 이하의 수)
for (int i = 0; i < Party.size(); i++) {
if (Party[i].Flag1) {
double Res = 17.0 * Party[i].P;
double Remain = Res - floor(Res);
Party[i].T = floor(Res);
Now_Total_T += Party[i].T;
Vec.emplace_back(make_pair(i, Remain));
}
}
if (Now_Total_T < 17) {
sort(Vec.begin(), Vec.end(), Comp);
for (int i = 0; i < Vec.size(); i++) {
int X = Vec[i].first;
Party[X].T++;
Now_Total_T++;
if (Now_Total_T == 17) {
break;
}
}
}
}
bool Comp2(INFO A, INFO B) {
if (A.Total == B.Total) {
return (A.Name < B.Name);
}
return (A.Total > B.Total);
}
void Final_Calc() {
for (int i = 0; i < Party.size(); i++) {
Party[i].Total = Party[i].R + Party[i].S + Party[i].T;
}
sort(Party.begin(), Party.end(), Comp2);
}
void Print() {
for (int i = 0; i < Party.size(); i++) {
cout << Party[i].Name << " " << Party[i].Total << "\n";
}
}
int main() {
FIRST
cin >> P >> V;
Party.resize(P);
for (int i = 0; i < P; i++) {
string A;
int B, C;
// 정당명, 지역구 의석(R). 비례대표국회의원선거 득표수를 입력받는다.
cin >> A >> B >> C;
Party[i].Name = A;
Party[i].R = B;
Party[i].Vote = C;
Party[i].IDX = i + 1;
True_Vote += Party[i].Vote; // 실득표 수의 합을 구한다.
}
init();
First_Step();
Third_Step();
Final_Calc();
Print();
return 0;
}'BOJ > Platinum ~ Diamond' 카테고리의 다른 글
| [BOJ/Platinum 5] 백준 20541 앨범정리(C++) (0) | 2022.02.02 |
|---|---|
| [BOJ/Platinum 5] 백준 17377 Taxi(C++) (0) | 2022.02.01 |
| [BOJ/Platinum 5] 백준 2505 두 번 뒤집기(C++) (0) | 2022.01.30 |
| [BOJ/Platinum 4] 백준 3111 검열(C++) (0) | 2022.01.29 |
| [BOJ/Platinum 4] 백준 12094 2048 (Hard)(C++) (0) | 2022.01.28 |