등수 매기기[2012번]

	# 백준 2012번 등수매기기 문제 링크 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다.  www.acmicpc.net

 

문제해설

 

이 문제는 그리드 문제이며 간단하게 생각해보면 기대등수를 오름차순으로 정리하여 실제 등수를 배정하게 되면 불만도의 합은 최소가 되게된다. 입력값이 커지게 되면 시간초과가 발생함으로 sys.stdin.readline을 사용하여 시간을 줄여주는것이 필요하다.

import sys
input=sys.stdin.readline #시간초과 방지

n=int(input()) 
rank=[] #각각의 예상등수를 담는 리스트
for i in range(n): #각각의 예상등수 입력받기
    rank.append(int(input()))

rank.sort() 
total=0#전체 불만도를 담기위한 변수
for i in range(0,n):#불만도 계산
    total+=abs(i+1-rank[i])
print(total)#출력