[1417]국회의원 선거

1. 문제

2. 알고리즘 + 풀이

초기 코드 -> 

# -*- coding: euc-kr -*-
import sys
import io


sys.stdout = io.TextIOWrapper(sys.stdout.detach(), encoding = 'utf-8')
sys.stderr = io.TextIOWrapper(sys.stderr.detach(), encoding = 'utf-8')

N = int(input())
lst = [0] * N #이렇게 초기화를 해야지, 대입 연산자 사용 가능
cnt = 0

for i in range(N):
    lst[i] = int(input()) 

key = lst[0] #다솜이가 기준
for i in range(1,N): #i=0이 다솜이 -> i=1부터 탐색
    if (key <= lst[i]):
         while not (key > lst[i]):
             lst[i]-=1
             key +=1
             cnt+=1
             

print(cnt)

1. 다솜이는 기호 1번 후보 => 따라서 코드에서 key = lst[0]는, 다솜이가 받은 득표 수 의미
2. lst[i]에서 i는 각각의 후보를 의미하고 lst[i]의 값은 해당 후보가 받은 표의 수입니다.
3. while not (key > lst[i]) 루프 안에서 lst[i]-=1와 cnt+=1이 실행되는 것은 다솜이가 다른 후보보다 많은 표를 얻기 위해 필요한 최소한의 매수 수를 계산하는 것

=> 입력 예시처럼 잘 나왔지만, 백준에서 틀렸다고 채점되었다

'최소 매수'를 구해야 한다는 것을 생각 안한 듯 하여, 반례를 찾아봄


7787 일 경우, 7787 -> 8687 -> 9677 로 총 2번 매수해야 한다.(sort하지 않고, 순서대로 한다면)

반례) BUT 2번 매수할 필요가 없음 =>  최소로 매수해야 하므로 7787 -> 8777 로 매수할 수가 있다!

즉, 최소 매수를 위해서는 최대를 찾아야 했다!

수정한 코드

N = int(input())
lst = [0] * N #이렇게 초기화를 해야지, 대입 연산자 사용 가능
cnt = 0

for i in range(N): #i=0,1,...N-1
    lst[i] = int(input()) 

key = lst[0] #다솜이가 기준
others = lst[1:]

others.sort(reverse=True) #나머지 후보들 득표수 내림차순 정렬
while (key <= others[0]):
    others[0]-=1
    key +=1
    cnt+=1
    others.sort(reverse=True) 
        
print(cnt)

 

=> 런타임 에러 발생

런타임 에러 발생 이유

 

others 리스트가 비어 있는 경우에 others[0]를 참조하려고 시도하기 때문

N = int(input())
lst = [0] * N #이렇게 초기화를 해야지, 대입 연산자 사용 가능
cnt = 0

for i in range(N): #i=0,1,...N-1
    lst[i] = int(input()) 

key = lst[0] #다솜이가 기준
others = lst[1:]

others.sort(reverse=True) #나머지 후보들 득표수 내림차순 정렬
while others and key <= others[0]: # others가 비어있지 않고, 다솜이가 가장 많은 표를 가질 때까지
    others[0]-=1
    key +=1
    cnt+=1
    others.sort(reverse=True) 
        
print(cnt)

while others and key <= others[0]:

others 리스트가 비어 있지 않고, 다솜이의 득표 수가 가장 많은 후보의 득표 수 이하일 때만 while 루프를 계속 실행하도록 함.

=> 이렇게 하면 others 리스트가 비어 있을 때 others[0]에 접근하려는 시도를 방지할 수 있다.

최종 코드(성공)

N = int(input())
lst = [0] * N #이렇게 초기화를 해야지, 대입 연산자 사용 가능
cnt = 0

for i in range(N): #i=0,1,...N-1
    lst[i] = int(input()) 

key = lst[0] #다솜이가 기준
others = lst[1:]

others.sort(reverse=True) #나머지 후보들 득표수 내림차순 정렬
while (key <= others[0]):
    others[0]-=1
    key +=1
    cnt+=1
    others.sort(reverse=True) 
        
print(cnt)

라이싱