[Algorithm] [백준] 1417 - 국회의원 선거 (그리디)

<첫번째 시도>

import sys
input = sys.stdin.readline

n = int(input())  # 후보의 수 n명

lst = [0]
for _ in range(n):
    lst.append(int(input()))
print(lst)

cnt = 0  # 매수해야 하는 사람
if lst.count(max(lst)) == 1 and max(lst) == lst[1]:
    print(0)
else:
    while True:
        for i in range(2, n+1):
            if lst[i] >= lst[1]:
                lst[i] -= 1
                lst[1] += 1
                cnt += 1
        if lst.count(max(lst)) == 1 and max(lst) == lst[1]:
            print(cnt)
            break

백준에 나와있는 입력값 전부 맞게 나오고.. 서치해서 찾아본 반례들도 제대로 나오는데 뭐가 문제일까 싶었다.

최소 매수를 구해야 한다는 것을 다시 생각하며 반례를 찾아보았다.

7787 일 경우, 7787 -> 8687 -> 9677 로 총 2번 매수해야 한다.

💥반례) 하지만 2번 매수할 필요가 없다. 최소로 매수해야 하므로 7787 -> 8777 로 매수할 수가 있다!

그러기 위해서는 나머지 2~n번까지 중 최대를 찾아서, 그 값을 다솜이(1번)와 비교하여 계산해야 한다.

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

<두번째 시도>
첫번째 시도에서는 2번 인덱스부터 차례대로 다솜이와 비교했지만,
이제 2번부터 n번까지의 최대값을 찾아 다솜이와 비교하는 코드를 추가했다.

import sys
input = sys.stdin.readline

n = int(input())  # 후보의 수 n명

lst = [0]
for _ in range(n):
    lst.append(int(input()))

cnt = 0  # 매수해야 하는 사람
if lst.count(max(lst)) == 1 and max(lst) == lst[1]:  # 다솜이의 표 수가 max이고, max는 다솜이 뿐 일 때!
    print(0)
else:
    while True:
        find_max = 0
        find_max_index = 0
        for i in range(2, n+1):  # 2번부터 n번까지 표 수 중 max 찾기
            if lst[i] > find_max:
                find_max = lst[i]
                find_max_index = i

        if find_max >= lst[1]:  # 찾은 max와 다솜이 비교하기
            lst[find_max_index] -= 1
            lst[1] += 1
            cnt += 1

        if lst.count(max(lst)) == 1 and max(lst) == lst[1]:  # 비교 후, 다솜이가 유일한 max이면 출력
            print(cnt)
            break

성공 !!