시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 591 72 59 17.456%

문제

정당들의 지역구 의석 수와 비례대표 득표 결과가 각각 주어질 때, 각 정당이 21대 국회의원 선거 결과에 따라 얻게 되는 총 의석 수를 각각 계산해 보자. 의원정수는 300명이며 지역구국회의원이 253명, 비례대표국회의원이 47명이다.

비례대표 의석은 비례대표국회의원선거 유효투표총수의 3% 이상을 득표했거나 지역구국회의원선거에서 5석 이상의 의석을 차지한 정당에만 배분된다(봉쇄조항). 비례대표 의석을 배분받는 정당을 의석할당정당이라 한다. 제21대 국회의원 선거에 한해, 비례대표 의석 배분 방식은 다음과 같다.


(1단계) 30석에 대해 전국단위 준연동(연동비율 50%) 방식으로 각 정당별 연동배분의석수 산정

의석할당정당이 비례대표국회의원선거에서 얻은 득표비율에 따라 산정한 의석수에서 해당 정당의 지역구국회의원 당선인 수를 뺀 후, 그 수의 50%에 이를 때까지 해당 정당에 비례대표 국회의원 의석을 먼저 배분한다.

\[\frac{\left(N-R\right)\times p_i - r_i}{2}\]

(\(N\): 국회의원 정수, \(R\): 의석할당정당이 아닌 정당의 지역구 당선인 수 총합 + 무소속 지역구 당선인 수, \(p_i\): 해당 정당의 비례대표국회의원선거 득표비율, \(r_i\): 해당 정당의 지역구국회의원 당선인 수)

\(p_i\)는 전체 유효표에 대한 득표비율이 아니고, 의석할당정당의 득표수를 모든 의석할당정당의 득표수의 합계로 나누어 다시 산출됨에 주의한다.

결과값은 1보다 작을 경우 0이며, 이외의 경우 소수점 첫째 자리에서 반올림한다. 이렇게 계산된 정수를 연동 배분 의석 수 \(s_i^\prime\)이라 한다.

\(s_i\)의 합이 30인 경우 이 의석 수를 47석 중 30석에 대한 해당 정당의 비례대표 의석 수(\(s_i\))로 확정한다.


(2-1단계) 각 정당별 연동배분의석수의 합계 < 30석일 경우 ☞ 잔여의석에 대해 기존 의석배분방식(병립형) 적용 배분

1단계에서 배분한 의석의 합이 30석을 넘지 못하여 잔여의석이 생기면, 잔여의석은 비례대표국회의원선거의 득표비율에 따라 산정한 의석을 배분한다.

\[s_i^\prime + \left(30-\sum s^\prime \right) \times p_i\]

(\(p_i\): 해당 정당의 비례대표국회의원선거 득표비율)

계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 30석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 30석에 대한 조정된 비례대표 의석 수 \(s_i\)라 한다.


(2-2단계) 각 정당별 연동배분의석수의 합계 > 30석 ☞ 각 정당별 연동배분의석수비율대로 배분

1단계에서 배분한 의석의 합이 30석을 넘어 초과의석이 생기면, 각 정당별 연동배분의석수비율대로 다시 배분한다.

\[\frac{30 \times s_i^\prime}{\sum s^\prime}\]

계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 30석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 30석에 대한 조정된 비례대표 의석 수 \(s_i\)라 한다.


(3단계) 17석에 대해 기존 의석배분방식(병립형) 적용 배분

나머지 17석에 대해 비례대표국회의원선거의 득표비율에 따라 산정한 의석을 배분한다.

\[17 \times p_i\]

(\(p_i\): 해당 정당의 비례대표국회의원선거 득표비율)

계산된 값의 정수 부분을 먼저 배분하고, 나머지는 총 연동배분의석수가 17석이 될 때까지 소수점 이하의 수가 큰 순서대로 배분한다. 이렇게 배분이 끝난 각 정당의 의석 수를 47석 중 17석에 대한 비례대표 의석 수 \(t_i\)라 한다.


최종적으로 정당 \(i\)의 비례의석은 \(s_i + t_i\)석이며, 지역구의석 수 \(r_i\)와 합치면 해당 정당이 21대 국회에서 얻는 총 의석 수는 \(s_i+t_i+r_i\)가 된다.

입력

첫째 줄에는 선거에 후보를 낸 정당의 수 \(P\)와 총 투표자 수 \(V\)가 주어진다. (\(1 \leq P \leq 50\)), (\(1 \leq V \leq 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\) = 기호 정당명 \(r_i\) = 지역구 의석 득표율
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\) = 기호 정당명 \(r_i\) = 지역구 의석 \(p_i\) = 비례득표율 \(s_i^\prime\) = 연동 배분 의석
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\) = 기호 정당명 \(s_i^\prime\) = 연동 배분 의석 \(s_i\) = 조정된 비례대표 의석
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\) = 기호 정당명 \(p_i\) = 비례득표율 \(t_i\) = 연동 배분 의석
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\) = 기호 정당명 \(r_i\) \(s_i\) \(t_i\) 합계의석
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호)을 기준으로 한다. 다만, 아래의 예외를 적용한다.

  • 의석을 소수점 이하의 수가 큰 순서대로 배분하는 상황에서, 소수점 이하의 수가 완전히 같다면 기호가 더 작은 정당에 먼저 배분한다. (이런 경우 선거법에서는 추첨에 따르도록 되어 있다.)

적어도 한 정당 이상은 \(s_i^\prime>0\)임이 보장된다.

출처