[BOJ] 21758 - 꿀 따기 (Python)

 

 

아이디어

 

벌통이 두 벌들보다 왼쪽이나 오른쪽에 있는 경우는 벌 한 마리와 벌통을 양쪽 끝에 배치하는 것이,

벌통이 두 벌들 사이에 있는 경우는 벌 두 마리를 양쪽 끝에 배치하는 것이 가장 많은 꿀을 딸 수 있다.

전자는 나머지 벌 한 마리의 위치를 조정하면서 최댓값을 찾고, 후자는 벌통의 위치를 조정하면서 최댓값을 찾는다.

 

 

풀이

 

벌들이 왼쪽에서 출발하는 누적합과 오른쪽에서 출발하는 누적합을 각각 left와 right 리스트에 저장한다.

결과값을 벌통이 두 벌들 가운데 있는 경우의 최댓값으로 초기화한다.

차례로 남은 벌의 위치를 조정하여 현재 최댓값과 출발 위치에 따른 두 값들을 비교해 결과값을 갱신해 나간다.

 

N = int(input())
honey = list(map(int, input().split()))
left = honey[:]
right = honey[::-1]
for i in range(N-1):
    left[i+1] += left[i]
    right[i+1] += right[i]
res = left[-1]-left[0]-right[0]+max(honey[1:-1])
for i in range(1, N-1):
    res = max(res,
              left[-1]*2-left[0]-left[i]-honey[i],
              right[-1]*2-right[0]-right[i]-honey[-(i+1)])
print(res)