[BOJ/백준] 2670번 연속부분최대곱 (Python 파이썬)

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

2670번: 연속부분최대곱

 

문제

N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

예제 입력 1

8
1.1
0.7
1.3
0.9
1.4
0.8
0.7
1.4

예제 출력 1 

1.638

 

---

풀이

문제를 살펴보면, 연속된 수열 중에서 곱의 결과가 가장 큰 경우를 찾아야 합니다. 

우선, i을 마지막으로 하는 수들의 곱에서 최대값을 담는 dp 리스트를 선언하였습니다. 

이제 loop을 돌며 dp[i]을 하나씩 계산하면 됩니다. i번째 값에는 "i을 마지막으로 하는 수열"들 중에서 수들의 곱이 최대인 수열을 고르고, 그 곱의 결과가 담길 것입니다. (dp[i[) 

그럼, (1) i를 마지막으로 하는 수열을 잇는다. (2) 수열을 이으면 손해이니 i을 다시 수열의 시작으로 정한다. 이렇게 2개의 선택이 있습니다. 

단순하게, 곱셈이므로 이전 수열의 곱셈이 1보다 크거나 같다면 수열을 이어도 됩니다.

아래 그림을 보시면, 1.3의 경우 이전 수열들의 최대곱이 0.77로, 곱하며 손해이므로 수열이 이어지지 않습니다.

 

Code

import sys
input = sys.stdin.readline
N = int(input())
# i을 마지막으로 하는 수들의 곱에서 최대값
dp = [float(input()) for _ in range(N)]

# 1부터 시작해야 dp[i-1]에서 dp[-1]으로 잘못 곱해지지 않음
for i in range(1, N):
    dp[i] = max(dp[i], dp[i]*dp[i-1])
print('%0.3f' % max(dp))