[백준/Python] #17127 벚꽃이 정보섬에 피어난 이유

문제

 

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

 

---

Algorithm

 

구간을 총 4개를 나누어야 하므로 for문을 3개 사용하여 구간을 나누었다.

 위 그림과 같이 for문으로 구간을 나누어 주었다. 최소한 그룹에는 1개의 나무가 존재해야 하므로 구간을 0~n-1로 설정하고 i는 j,k를 고려하여 0~n-3까지, j는 k를 고려하여 1자리를 남겨야 하므로 i+1부터 n-2까지, k는 j+1부터 n-1까지 설정해준다.

이제 구간끼리의 곱을 구해야 한다. 우리가 설정한 i,j,k에 따라 구간은 [0,i] , [i+1,j] , [j+1,k] , [k+1,n-1]의 구간이다.
여기서 누적합의 개념을 사용해서 누적합이아닌 누적곱으로 바꾸어 주었다. prefix[0] = 1로 설정하고 계속 곱하고, 첫 구간[0,i]구간의 곱은 prefix[i+1]//prefix[0]와 같이 나타낼 수 있다. 

모든 구간의 곱들의 합은 prefix[i+1]//prefix[0]+prefix[j+1]//prefix[i+1]+prefix[k+1]//prefix[j+1]+prefix[n]//prefix[k+1]과 같이 나타난다. 즉, 구간 끝점 +1의 index // 구간 시작점의 index값으로 나타내지고 이를 더한 다음 최대값을 구하면 되는 문제이다.

---

 

 

Code

input = __import__('sys').stdin.readline

n = int(input())
count = list(map(int,input().split()))
prefix = [1]
ans = -1

for i in range(1,n+1):
    prefix.append(prefix[i-1]*count[i-1])

for i in range(0,n-3):
    for j in range(i+1,n-2):
        for k in range(j+1,n-1):
            sum = prefix[i+1]//prefix[0]+prefix[j+1]//prefix[i+1]+prefix[k+1]//prefix[j+1]+prefix[n]//prefix[k+1]
            ans = max(ans,sum)

print(ans)