• 시간 : 50개 테스트케이스를 합쳐서 C의 경우 5초 / C++의 경우 5초 / Java의 경우 10초 / Python의 경우 20초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

도토리 놀이공원을 운영하는 홍준이는 자신의 놀이공원에 어린이가 매우 적다는 것을 알게 되었다.

“놀이공원을 빛내는 사람들은 아이들이다.”라는 철학을 가진 홍준이는 이 사실에 충격을 받았고, 어린이 손님을 모으기 위해 열심히 노력하기로 결심했다.

그 첫 번째는 느린 롤러코스터를 만드는 것이다.

홍준이는 롤러코스터를 만들기 위해 N개의 레일을 구입했지만, 어떤 순서로 조립해야 가장 느린 롤러코스터를 만들 수 있는지 알 수 없었다.

먼저, 롤러코스터는 여러 개의 레일을 이어서 만든다.

각 레일에는 두 개의 자연수 a, b가 주어져 있다.

차량은 레일을 통과하면서 속도가 증가하게 되며, 진입할 때의 속도가 v였다면 통과한 이후에는 av+b가 된다.

롤러코스터를 출발할 때 차량의 속도는 1이며, 롤러코스터의 모든 레일을 지났을 때 차량의 속도를 최소한으로 줄여야 한다.

홍준이는 레일을 버리는 것을 싫어하기 때문에, N개의 레일을 모두 사용하여 롤러코스터를 만들어야 한다.

홍준이를 도와 가장 느린 롤러코스터를 만들어주자!


[입력]

첫째 줄에 레일의 개수 n (2 <= n <= 200000)이 주어진다.

둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다.

a와 b는 1000000000 이하의 자연수이다.

[출력]

각 테스트케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다.)를 출력하고 한 칸을 띄운 후,

모든 레일을 통과했을 때 속도의 최솟값을 1000000007으로 나눈 나머지를 출력한다.
 

이런 문젠데 푸는 아이디어는 정렬해서 푸는거고 코드는 다음과 같습니다.

다른언어 풀이를 보니 모두 비슷한 아이디어고 이렇게 푸는게 맞는거 같은데 시간초과라고 뜨고

설상가상으로 테스트케이스 아웃풋을 모두 모아서 한번에 출력하면 오답처리 됩니다(다른 문제는 이렇게 풀어도 문제 x)

왜 이런거죠? 혹시 이거 파이썬으로 푸신분들 어떻게 푸셨나요

ans = []
for tc in range(1, int(input()) + 1):
    rails = [tuple(map(int, input().split())) for _ in range(int(input()))]
    rails.sort(key=lambda x: ((x[0] - 1) / x[1]), reverse=True)

    result = 1
    for a, b in rails:
        result = (a * result) + b

    ans.append(result % 1000000007)

for i in range(len(ans)):
print(f'#{i + 1} {ans[i]}')