파이썬) 백준 알고리즘 | 2670번 : 연속부분최대곱

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

2670번: 연속부분최대곱

백준 2670 '연속부분최대곱' 문제입니다.

 

처음에 그냥 곱하는 모든 경우의 수를 구했었는데 시간초과가 떠서

리스트에 곱해서 저장을 하였습니다.

예를 들어 입력으로 1,2,3,4,5 이렇게 들어온다면

리스트에는 1,1,2,6,24,120 이런 식으로 들어가게 만들고 인덱스를 이용해서

j번째를 i번째로 나눠준다면 i+1부터j까지의 곱이 됩니다.

그런데 중간에 0이 들어가게 된다면 0이후에 리스트값이 나 0이 되기 때문에

0이 나오면 분할해서 저장하였습니다.

 

아래는 코드입니다.

N = int(input())
nums = []
num = [1]
score = 1
for i in range(N):
    a = float(input())
    if a == 0:
        nums.append(num)
        num = [1]
        score = 1
    else:
        score *= a
        num.append(score)
nums.append(num)

result = 0
for n in range(len(nums)):
    for i in range(len(nums[n])):
        for j in range(i+1, len(nums[n])):
            mul = nums[n][j] / nums[n][i]
            result = max(result, mul)
print("{:.3f}".format(result))