[백준] 1900 레슬러 (파이썬), 시간 초과 해결하는 법

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

1900번: 레슬러

 

만나는 순서를 어떻게 짜더라도 '그가 이긴 경기 수'는 변하지 않는다. 따라서 이는 고려하지 않고 '선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수'만 고려하면 된다. N이 크다는 점과 단순히 강한 순서대로 나열하면 되지 않을까하는 아이디어를 바탕으로 정렬 알고리즘을 시도해본다.

선수 i가 선수 j를 이긴다.
= 힘i + 링i*힘j > 힘j + 링j*힘i
= 힘i(1-링j) > 힘j(1-링i)
= (1-링j)/힘j > (1-링i)/힘i
= xj > xi, 단 xi=(1-링i)/힘i

이제부터 '선수들의 힘은 수직선 상에 위치한 정수이다'로 문제를 변환할 수 있고 이는 훨씬 쉬운 문제이다.

힘의 크기대로 정렬을 하면 '선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수'가 0이 되어 수여하는 금화의 수를 최소화할 수 있다. 왜냐하면 이 정렬에서는 자기보다 앞에 있는 선수에 대해 언제나 자기가 지기 때문이다.

한편 수직선 상에 위치한 힘을 바탕으로 할 때, 승수는 애초에 힘의 크기의 순위로 계산할 수 있기 때문에 자기보다 승수가 높은 선수는 자기보다 힘의 크기가 좋다. 따라서 그 선수에 대해 자기가 이기는 경우는 없다. 따라서 승수에 대해 정렬을 해도 마찬가지로 추가적으로 수여하는 금화의 수가 0이 되어 총 금화의 수를 최소화할 수 있다.(ㄱ)

nC2 브루트포스로 구한 승수를 바탕으로 별 다른 증명 없이 (ㄱ)의 성질만을 이용하여 승수로 정렬하는 풀이가 인터넷에는 많지만 이러한 풀이로는 정답임을 증명하지 못한다.

 

import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
players = []
for i in range(N):
    index = i+1
    power, ring = map(int, input().split())
    players.append((index, power, ring))

players.sort(key=lambda x: (1-x[2])/x[1])

for player in players:
    print(str(players[0])+'\n')