[#알고리즘/DP/[백준]21758번: 꿀 따기(python)]

Question

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

Solution

벌통 자리가 될 수 있는 위치는 아래와 같다.

1. 맨 오른쪽 끝
2. 맨 왼쪽 끝
3. 가운데

벌통 자리를 어느 위치로 설정했을 때, 딸 수 있는 꿀의 양이 많은 지를 비교한다. 처음 장소(맨 왼쪽)부터 각 장소까지 얻을 수 있는 꿀의 누적합을 구해놓고, 그걸 사용하여 문제를 해결한다.

1번과 2번의 경우, 한 마리의 벌은 반드시 반대쪽 끝에 존재해야 한다. 벌은 반드시 벌통 쪽으로 이동해야하는데, 최대한 한 장소라도 더 거쳐서 꿀을 더 따야하기 때문이다. 이때, 양쪽 끝 장소를 제외한 가운데 장소들 중 나머지 벌 한 마리의 장소만 탐색하면 된다.

3번의 경우 두 마리의 벌은 반드시 양 끝에 존재한다.

Code

import sys
from unittest import result

input = sys.stdin.readline

# 꿀통이 왼쪽 혹은 오른쪽 끝에 있을 경우   
def end_honey(data, sum) :  
    max_honey = 0
    
    # 꿀통이 왼쪽 끝에 있을 경우 (벌1은 무조건 오른쪽 끝에 존재)
    for i in range(1, n - 1) :
        # 얻을 수 있는 꿀의 양 = 벌1이 얻는 양 + 벌2가 얻는 양 - 벌2가 위치한 장소의 꿀의 양 (벌1은 벌2 위치에서 꿀을 따지 못함.)
        max_honey = max(max_honey, sum[-2] + sum[i - 1] - data[i])

    # 꿀통이 오른쪽 끝에 있을 경우 (벌1은 무조건 왼쪽 끝에 존재)
    for i in range(1, n - 1) :
        # 얻을 수 있는 꿀의 양 = 벌1이 얻는 양 + 벌2가 얻는 양
        max_honey = max(max_honey, (sum[-1] - data[0] - data[i]) + (sum[-1] - sum[i]))
        
    return max_honey
    
# 꿀통이 가운데에 위치할 경우 (벌1과 2는 무조건 양쪽 끝에 존재)
def middle_honey(data, sum) :
    return (sum[-2] - data[0] + data[n // 2])

n = int(input())
data = list(map(int, input().split()))
answer = 0
sum = []

# 각 위치에서 이전까지 얻을 수 있는 꿀의 누적합 계산하여 저장
for i in data :
    answer += i
    sum.append(answer)
    
print(max(middle_honey(data, sum), end_honey(data, sum)))