[알고리즘/백준] 2012번 등수 매기기 Python 파이썬

 

이번 게임은 쉽게 풀 수 있음에도 어렵게 생각해 헤매었던 문제였습니다.

 

 

각 사람의 예상 등수가 주어지고 임의로 등수를 지정했을 때 그 차이의 합을 최소로 하는 프로그램을 작성하는 문제였습니다. 처음에 문제를 풀이할때는 일단 등수 별로 넣어주고 동점자여서 들어가지 못한 점수들을 배치해줄려고 했는데 최솟값이라고 하니 이때 어떻게 최소 차이 등수랑 매칭해줄지(양방향 검사가 필요해짐) 머리가 복잡해졌습니다. 풀다보니 뭔가 이렇게 푸는게 아닌 것 같아 결국 다른 분들의 풀이를 찾아보았고 그리디 알고리즘에 대해 알 수 있었습니다.

 

그리디 알고리즘이란?

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다.

 

사실 위의 알고리즘을 어떻게 활용하면 좋을지 백프로 이해되지는 않지만 이를 통해 생각해보면 각자 생각한 예상 등수를 나열시킨 후 비교한다면 차이값이 최소가 될 수 있다는 것을 깨달을 수 있었습니다. 

 

다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
score = []

for i in range(n):
    score.append(int(input()))

score.sort()

rank = [i for i in range(1,n+1)]
answer = 0

for i in range(n):
    answer += abs(rank[i] - score[i])

print(answer)

 

이렇게 간단하고 짧은 코드로 풀리는 문제를 쓸데없이 길게 붙잡고 있었네요. 그리디 알고리즘을 좀 더 이해하고 싶으면 배낭 문제나 수업 배치 문제를 접하고 풀어보면 좋은 것 같습니다.