[ 2670 ] [ DP ] 연속부분최대곱

문제 설명

---

문제

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

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

입력

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

출력

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

---

풀이 과정

---

1. 현재 위치를 i라고 할 때, i에 올수 있는 경우는 두가지이다.

   • 이전까지의 곱에 i를 곱하는 경우
   • i에서 시작하는 경우

2. 따라서, 두가지 경우중 최댓값을 dp[i]로 설정해주면 된다.

3. 마지막으로, 출력 형식을 잘 보아야 함.

   • 4번째 자리에서 반올림 시킨후 소수점 셋째자리까지 출력해주어야 함.
   • 1 (x) 1.000 (o)

---

소스 코드

---

import sys

input = sys.stdin.readline

N = int(input().rstrip())
numbers = [float(input().rstrip()) for _ in range(N)]
dp = [0] * N

dp[0] = numbers[0]

for i in range(N):
    if i > 0:
        dp[i] = max(dp[i-1] * numbers[i], numbers[i])

print("%.3f"%(round(max(dp), 3)))