본문 바로가기

BOJ 알고리즘 (패캠)/탐욕, 백트래킹

2012번: 등수 매기기 (탐욕)

www.acmicpc.net/problem/2012

 

2012번: 등수 매기기

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

www.acmicpc.net

# 등수 매기기
# https://www.acmicpc.net/problem/2012 (탐욕)

import sys


def run(N, pre_ranks):
    pre_ranks.sort()  # ((예상 등수 순서로 선택해서)) 랭킹을 매긴다

    res = 0
    for i in range(N):
        rank = i + 1
        res += abs(pre_ranks[i] - rank)

    return res


N = int(input())
pre_ranks = [int(sys.stdin.readline()) for _ in range(N)]

print(run(N, pre_ranks))

'BOJ 알고리즘 (패캠) > 탐욕, 백트래킹' 카테고리의 다른 글

1461번: 도서관 (탐욕)  (0) 2020.10.23
2212번: 센서 (탐욕)  (0) 2020.10.23
1092번: 배 (탐욕)  (0) 2020.10.23
1439번: 뒤집기 (탐욕)  (0) 2020.10.22
5585번: 거스름돈 (탐욕)  (0) 2020.10.22