백준 17127번 벚꽃이 정보섬에 피어난 이유 - 파이썬(Python)

백준 17127번

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

 

정답코드) 시간: 44ms

- 4개 구간이 연속적으로 놓이므로, 구간 사이의 칸막이 3개 위치를 하나씩 옮겨가며 모든 경우를 다 계산해본다.
- 예를 들어 n = 6이고 각 구간의 나무를 O로 표시한다면, 아래처럼 뒤쪽 칸막이부터 차례로 옮긴다. (for문을 이용)
O / O / O / O O O
O / O / O O / O O
O / O / O O O / O
O / O O / O / O O
O / O O / O O / O
(...)
- 칸막이 위치, 즉 각 구간의 마지막 원소 인덱스를 i, j, k, l로 두었다.

n = int(input())
nums = list(map(int, input().split()))
ans = 0
ires = 1
for i in range(0, n-3):
    ires *= nums[i]
    jres = 1
    for j in range(i+1, n-2):
        jres *= nums[j]
        kres = 1
        for k in range(j+1, n-1):
            kres *= nums[k]
            lres = 1
            for l in range(k+1, n):
                lres *= nums[l]
            ans = max(ans, ires+jres+kres+lres)
print(ans)