[BEAKJOON] 백준 14698번 : 전생했더니 슬라임 연구자였던 건에 대하여 - 파이썬

제목이 너무 재미있다.

 

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

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

 

 

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어지고, 이어서 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 슬라임의 수 N (1 ≤ N ≤ 60)이 주어지고, 두 번째 줄에는 N 개의 자연수가 주어진다. i번째 자연수 Ci (2 ≤ Ci ≤ 2 × 1018) 는 i번째 슬라임의 슬라임 에너지를 나타낸다. 끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 1018 이하라는 것이 보장된다.

모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다.

(이 말의 뜻은, mod 계산을 해줄 때, 항상 long 보다 작으니, 건들지 말라는 것이다.)

 

출력

각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다.

 

---

첫번째 예제를 보면, 

3, 10, 2, 8, 14

3 x 10 = 30,

30 x 2 = 60,

60 x 8 = 480,

480 x 14 = 6,720

 

30 x 60 x 480 x 6720 = 5,806,080,000

(3 x 10) x (3 x 10 x 2) x (3 x 10 x 2 x 8) x (3 x 10 x 2 x 8x 14) 을 곱하는 것을 확인할 수 있고,

즉, 여기서 앞에서 곱한 값은 계속해서 더해주는 것을 확인할 수 있었다.

 

슬라임을 합성해서 가장 작은 값을 하려고 하면, 앞의 부분의 값이 적어야 한다는 프로세스가 나온다.

 

 

시간초과 코드

import sys
from functools import reduce

T = int(sys.stdin.readline())

while(T):
    T -= 1
    num = int(sys.stdin.readline())
    input_list = list(map(int, sys.stdin.readline().split()))
    input_list = sorted(input_list, reverse=True)
    result = []
    total_result = 1
    if(num != 1):
        for i in range(1, num):
            tmp = input_list[-1] * input_list[len(input_list)-2]
            input_list.pop()
            input_list[-1] = tmp
            result.append(tmp)
            input_list = sorted(input_list, reverse=True)
        total_result = reduce(lambda x, y : x*y, result)%1000000007
    print(total_result)

 

그래서 아주 조금 최적화 방향으로 수정해주었더니 해결 완료!

어떤 것을 최적화를 시켰을까?

pop()함수를 조금 더 써주고, append()를 써주었다.

 

정답코드

import sys
from functools import reduce

T = int(sys.stdin.readline())

while(T):
    T -= 1
    num = int(sys.stdin.readline())
    input_list = list(map(int, sys.stdin.readline().split()))
    input_list = sorted(input_list, reverse=True)
    result = []
    total_result = 1
    if(num != 1):
        for i in range(1, num):
            tmp = input_list.pop() * input_list.pop()
            input_list.append(tmp)
            result.append(tmp)
            input_list = sorted(input_list, reverse=True)
        total_result = reduce(lambda x, y : x*y, result)%1000000007
    print(total_result)