[Python/BOJ] 1900. 레슬러

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

1900번: 레슬러

문제

옛날에 레슬링을 무척 좋아하는 동호라는 국왕이 살았다. 그 당시 레슬링 선수들은 초자연적인 힘을 가졌다. 경기에 이기기 위해서 레슬링 선수는 자신의 힘뿐만 아니라 경기할 때 착용하는 마술 링에도 의존한다. 마술 링은 레슬링 선수로 하여금 상대 선수의 힘에 비례하는 힘을 추가로 얻을 수 있게 해준다.

레슬링 선수의 힘과 마술 링의 힘은 모두 양의 정수이다. 선수 A가 선수 B와 경기할 때, A의 ‘경기력’은 ‘A의 힘’ + ‘B의 힘’ * ‘A가 착용하고 있는 마술 링의 힘’이다. 경기에서는 경기력이 높은 선수가 이긴다.

예를 들어, 선수 A의 힘이 10이고 착용하고 있는 마술 링의 힘은 3이라고 하고, 선수 B의 힘은 18이고 착용하고 있는 마술 링의 힘은 4라고 하자. 이 두 선수가 경기를 가지면, A가 이긴다. 왜냐하면, A의 경기력은 10+3*18=64이지만 B의 경기력은 18+4*10=58이기 때문이다. 만약 A가 힘이 15이고 마술의 힘이 5인 링을 착용한 선수 C를 만났다면, C가 이긴다. 이 경기에서 A의 경기력은 10+3*15=55이고 C의 경기력은 15+5*10=65이다. 마찬가지로 B와 C의 경기에서는 C가 이긴다.

동호는 매년 레슬링 축제를 연다. 축제 기간에 각 레슬링 선수는 다른 모든 선수들과 한번씩 경기를 가진다. 이 축제의 마지막에 동호는 레슬링 선수를 보두 초대하여 축하하고 금화를 수여한다.

레슬링 선수들이 동호를 만나는 줄(순서)를 정하는 것은 희현이 할 일이다. 이 일은 매우 중요하다. 왜냐하면, 동호가 수여하는 금화의 수는 그가 이긴 경기수와 그가 선수들의 줄 어느 위치에 서 있느냐로 결정한다고 선언하였기 때문이다. 한 선수가 받는 금화의 수는 그가 이긴 경기 수 + 선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수이다.

예를 들어 위의 세 선수 A, B, C에게 A, B, C의 순서로 동호를 만나면, A는 금화 1개, B는 0개, C는 4개를 받게 된다. C는 2 경기를 이겨서 2개에 자기가 이긴 A, B가 자기보다 줄에서 앞에 있으므로 각각 하나씩 2개를 합하여 4개를 받는다. 만약 C, A, B 순서라면 C는 2개, A는 1개, B는 0개를 받게 된다.

희현이는 나라의 재정을 고려하여 수여하는 금화의 수를 최소화하고자 한다. 당신이 할 일은 재무장관을 도와 수여하는 금화의 수를 최소화하도록 동호를 만나는 순서를 결정하는 것이다. 모든 선수들의 힘과 가진 마술 링의 힘이 주어진다. 경기에서 비기는 경우를 발생시키지 않는다고 가정한다.

입력

첫째 줄에 선수들의 수 N이 주어진다. 선수들은 1부터 N까지 번호가 붙어 있다. 다음 N개의 줄에는 한 줄에 한 선수의 힘과 그가 가진 마술 링의 힘이 주어진다. 선수 k의 정보는 k+1번째 줄에 주어진다. N은 10000 이하이고, 선수의 힘과 마술 링의 힘은 모두 1 이상 1000 이하라고 가정하여도 좋다.

풀이

Code

import sys
input = sys.stdin.readline

n = int(input())
players = [0] + [list(map(int, input().split())) for _ in range(n)]
# 1. 승리 횟수 딕셔너리 생성
win = {}
for i in range(1, n+1) : win[i] = 0
# 2.
for p1 in range(1, n+1) :
    for p2 in range(p1+1, n+1) :
        # 2-1. 승리한 선수의 승리 횟수 추가
        if players[p1][0] + players[p2][0] * players[p1][1] > players[p2][0] + players[p1][0] * players[p2][1] :
            win[p1] += 1
        else : win[p2] += 1
# 3. 이긴 횟수대로 결과 출력
for key, value in sorted(win.items(), key = lambda x : -x[1]) :
    print(key)