문제

명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 계속 할 수 있다. 하지만 명예 점수가 0 이하가 되는 순간 그들은 국회의원에서 박탈당하며 오랫동안 비난의 대상이 된다.

국회의원들에게 밀려 권력이 없는 왕은 프로젝트 “Defile”을 설계해 모든 국회의원을 없애버릴려고 한다. 프로젝트 “Defile”은 다음과 같은 방식으로 작동한다.

1. 모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시킨다.
2. (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.
3. (1)에 의해 국회의원에서 박탈당한 사람이 없다면 프로젝트를 종료한다.

프로젝트 자체가 명예롭지 못한 행동이기에 왕은 단 1번의 “Defile”을 실행해 모든 국회의원을 박탈시키고 싶다. 이를 위해 그는 전문해커집단 “제이나”에서 해커를 여러 명 고용했다. “제이나”에 소속된 각 해커는 사이버 상에 있는 흑역사를 추적해 국회의원 1명의 명예를 1만큼 감소시킬 수 있다. 이 역시 명예롭지 못하기에 왕은 최소한의 해커를 고용하려고 한다. 과연 왕은 최소 몇 명의 해커를 고용해야 할까?

# 16678
import sys
input = lambda: sys.stdin.readline().strip()

# n : 100,000 -> O(NlogN)
# 1부터 연속된 수로 오름차순 정렬 구성 목표

n = int(input())
arr = [int(input()) for _ in range(n)]
arr.sort()

hacker = 0
num = 1
    
for i in range(n):
    if arr[i] == num:
        num += 1
        continue
    elif arr[i] == num - 1:
        continue
    else:
        hacker += (arr[i] - num)
        arr[i] = num
        num += 1

print(hacker)

백준 16678 모독