[Python] 백준 2012_등수 매기기 : 그리디

 

https://www.acmicpc.net/problem/2012

2012번: 등수 매기기

 

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

→ 단순하게 현재 상황에서 가장 좋아보이는 것만 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다!

 

풀이 방법

1. 각 사람이 제출한 예상 등수를 오름차순으로 정렬한다.

2. 높은 등수부터 예상 등수의 차이를 각각 계산하여 불만도를 계산

→ 1~n까지의 등수와 오름차순으로 정렬된 예상등급의 차이를 계산하여 결과를 구함

 

그리디 알고리즘의 정당성

- '가장 큰 순위부터' 계산 = 그리디로 접근한 계산 방법

- 그리디 알고리즘으로 해법을 찾았을 때에는 해법이 정당한지 검토해야 한다!

→ 예상 등수를 정렬한 후 각 순위를 비교했기 때문에, 예상한 순위와 실제 순위의 차이가 최소화 된다.
그러므로 최소의 불만도를 계산할 수 있게 된다.

 

최종 코드

import sys
n = int(sys.stdin.readline().rstrip())
grades = []
for _ in range(n):
    grades.append(int(sys.stdin.readline().rstrip()))

grades.sort()
result = 0
for i in range(1, n + 1):
    result += abs(i - grades[i - 1])
print(result)