[Baekjoon 2012] 등수 매기기

문제

🤍Ⅲ [Baekjoon 2012 - 등수 매기기]

문제 풀이 방법

그리디 알고리즘은 처음 알고리즘을 설계할 때부터 최적의 해를 찾는 알고리즘을 생각해고 설계해야되기 때문에 어떤 경우에 최소의 불만도를 가질지 생각하는데 시간이 오래 걸렸다. 학생들의 예상등수를 오름차순으로 정렬한다. 이 때의 순서를 자신의 실제 등수라고 생각하는 경우 최소의 불만도를 가진다.

1. 입력받은 예상 등수를 오름차순으로 정렬한다.
2. 예상 등수의 순위를 실제 등수로 가정하고 불만도를 계산한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

N = int(input())
expected = [int(input()) for _ in range(N)]
expected.sort()

answer = 0
for i in range(N):
    answer += abs(expected[i] - (i+1))
print(answer)