[BOJ] 2670. 연속부분최대곱

문제

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

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

입력

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

출력

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

import sys  
input = sys.stdin.readline
n = int(input())
dp = []
for _ in range(n):
  dp.append(float(input()))
result = 0
for i in range(n):
  mul = 1
  for j in range(i, n):
    mul *= dp[j]
    dp[i] = max(mul, dp[i])
  result = max(result, dp[i])
print('%.3f'%(result))

출력할 때

print(round(result, 3))

이런 코드를 작성하면 틀리다고 나온다.. 이것때문에 10번 넘게 틀렸다.
왜인지는 모르겠지만, 이제는 %.3f 이렇게 작성해야겠다.

또 Python3로 채점 시, 시간 초과가 발생한다.
아마도 브루트포스 알고리즘을 이용하다보니 시간 초과가 발생하는 듯하다.

시간 제한이 1초이다보니 이렇게 푸는 게 맞나 긴가민가하다가
계속 틀려서 역시 이중 for문때문인가 했는데 반올림 때문이었다.
그래도 복습하면서 연속부분최대곱 더 익숙해져야지

---

21.04.14 Review

n = int(input())
arr = []

for _ in range(n):
  arr.append(float(input()))

ans = 0

for i in range(n):
  mul = 1
  for j in range(i, n):
    mul *= arr[j]
    ans = max(mul, ans)
  
print('%.3f'%(ans))

이번에는 for문에서 실수를 했다.

for i in range(n - 1):
  mul = arr[i]
  for j in range(i + 1, n):
    mul *= arr[j]
    ans = max(mul, ans)
  
print('%.3f'%(ans))

처음에

mul = arr[i]

이렇게 초기화했는데
초기화 상태에서만

ans = max(mul, ans)

max() 함수를 적용하지 않아서 틀린 것이다.
-> mul을 1로 초기화하고, for문에서 모두 비교를 할 수 있도록 수정했다.

---

21.07.09 복습

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
  arr.append(float(input()))

max_val = max(arr)
for i in range(n - 1):
  mul_val = 1
  sub_max_val = arr[i]
  for j in range(i, n):
    mul_val *= arr[j]
    sub_max_val = max(mul_val, sub_max_val)
  max_val = max(sub_max_val, max_val)

print('%.3f'%max_val)

round함수를 이용해 출력하는 것만 조심하면 될 듯하다..!