백준_16678_모독 (python)

★ 접근

국회의원의 수가 최대 십만 명 + 각 국회의원 당 주어지는 명예 최대 십만 + 해커가 국회의원 한 명의 명예를 떨어트리는 점수 겨우 1점 = > 그리디 알고리즘 

 

★ 풀이

(국회의원 명예 점수는 1부터 시작해서 1씩 늘어나게 존재해야 한다. 이유는 "Defile"를 계속 하기 위함이다)

1. .일단 먼저 명예 점수를 오름차순으로 정렬한다.

2. 1부터 시작해서 현재 국회의원과 점수가 다르다면

  2-1. 근데 현재 국회의원 점수가 크거나 같다면 차이를 빼서 더하면 된다. + 그리도 다음 num으로 넘어간다.

  2-2. 작다면 그냥 무시하고 다음 단계로 넘어간다. 이유는 현재 data[idx]가 3이고 num이 4라했을 명예를 늘릴 방법이 없고 늘릴 이유도 없다. 문제는 명예 점수를 줄이는 것이 목표다.

 

★ 코드

import sys
input = sys.stdin.readline
n = int(input())
data = []
for _ in range(n):
    honor = int(input())
    data.append(honor)
answer = []
num = 1
idx = 0
result = 0
data.sort()
while idx < len(data):
    if num != data[idx]:
        if data[idx] >= num:
            result += data[idx] - num
            num += 1
        else:
            pass
    else:
        num += 1
    idx += 1
print(result)

★ 회고

 처음에는 결국 명예 점수를 1~n 까지 맞추면 된다고 생각했기에 엄청 간단하게 문제 풀이를 했다. 하지만 n 보다 작은 수로만 이루어질 수도 있는 반례가 있었다.

그리디라고 생각하고 로직을 떠올렸을 때 반례까 있을지 없을지 한번 더 생각해보고 코드를 짜보자