이번 문제는 그리디 알고리즘을 통해 해결하였다. 처음에는 단순하게 정렬했을 때 1부터 1씩 증가하는 리스트가 만들어지면 된다고 생각하였다. 그러나 1 1 2 2 4와 같은 리스트가 입력된다면 다른 케이스가 발생한다. 다른 방법을 생각하던 중, 매 차례마다 사라져야 하는 수를 찾는 방식으로 접근해보았다.

• 첫번째 차례에는 1이 없어져야 한다. 2 3 4 6 7의 경우 2가 1보다 크기 때문에 문제가 성립하지 않는다. 이럴 경우 해커를 2-1명 추가하여 2를 지운다. 첫번째 차례에 없어질 국회의원을 정했기 때문에 두번째로 넘어간다. (answer = 1)
• 두번째 차례에는 2가 없어져야 한다. 0 3 4 6 7이기 때문에 3이 2보다 크기 때문에 해커를 3-2명 추가한다. 그리고 세번째로 넘어간다. (answer = 2)
• 세번째 차례에는 3이 없어져야 한다. 0 0 4 6 7이므로 4가 3보다 크기 때문에 해커를 4-3명 추가한다. 그리고 네번째로 넘어간다. (answer = 3)
• 네번째 차례에는 4가 없어져야 한다. 0 0 0 6 7이므로 6이 4보다 크기 때문에 해커를 6-4명 추가한다. 그리고 다섯번째로 넘어간다. (answer = 5)
• 다섯번째 차례에는 5가 없어져야 한다. 0 0 0 0 7이므로 7이 5보다 크기 때문에 해커를 7-5명 추가한다. 이렇게 되면 answer = 7이 되고, 리스트는 0 0 0 0 0이 된다.

Code

n = int(input())
man = sorted([int(input()) for _ in range(n)])
answer = 0
std = 1
for i in range(n):
    if man[i] >= std:
        answer += man[i] - std
        std += 1
print(answer)