[백준] 21758번 꿀 따기 (Python)

백준 21758 꿀 따기

숫자가 크고 nC3의 크기가 매우 큰 것을 봐선 조합을 활용해 최댓값을 구하는 것이 아니라고 생각했다. 즉, 그리디알고리즘을 활용해야 하고 필요한 규칙을 찾는 것이 중요했다. 문제의 포인트는 다음과 같다.

1. 가장 끝에 있는 요소는 어떠한 경우에도 추출할 수 없으므로 특별한 경우를 제외하면 가장 끝에서 추출하는 것이 유리하다.
2. 양 끝의 요소를 각각 벌집, 벌1로 지정한다.
3. 벌2는 모든 경우를 탐색하되, 점화식을 활용해 효율적으로 탐색한다.(이전 위치를 더하고 현재 위치를 2 번 뺀다.)
4. 요소가 3개인 특별한 경우는 3가지 요소 중에 최댓값 * 2를 반환한다.

import sys 

n = int(sys.stdin.readline().strip())
l = list(map(int, sys.stdin.readline().split()))
if len(l) == 3:
    print(2 * max(l))
    exit(0)

# 벌1 왼쪽, 벌집 오른쪽
b1 = 0
b2 = 2
h = len(l) - 1
s = 2 * sum(l[2:])
maxV = s
while b2 < h:
    s = s - 2 * l[b2] + l[b2 - 1]
    maxV = max(s, maxV)
    b2 += 1

# 벌1 오른쪽, 벌집 왼쪽
b1 = len(l) - 1
b2 = len(l) - 3
h = 0
s = 2 * sum(l[:-2])
maxV = max(s, maxV)
while b2 > h:
    s = s - 2 * l[b2] + l[b2 + 1]
    maxV = max(s, maxV)
    b2 -= 1
print(maxV)