[백준] 21758 - 꿀 따기

1. 문제

21758번: 꿀 따기

2. 개요

전에 풀다 던졌던 문제를 다시 잡아봤는데.. 또.. 화병날뻔했다.

벌이 따올 수 있는 꿀의 최댓값을 구하는 문제.

3. 코드 및 추가내용

처음엔 벌 두마리와 벌통이 있을 수 있는 모든 경우를 돌면서 탐색했더니 11점에서 개선될 여지가 보이지가 않았다.

해서 좀 더 고민해보니 최댓값을 얻을 수 있는 경우에는 양 끝에 벌이 있거나, 벌통이 존재하는 경우임을 깨달았다.

import sys
N = int(sys.stdin.readline())

honeys = list(map(int, sys.stdin.readline().split()))
ans = 0

def calc(l):
    global ans
    for i in range(3):
        b1, b2, honey = l[i%3], l[(i+1)%3], l[(i+2)%3]
        if b1 < honey < b2 or b2 < honey < b1:
            honeysum = sum(honeys[min(b1,b2)+1:max(b1,b2)]) + honeys[honey]
        elif b1 < honey and b2 < honey:
            honeysum = sum(honeys[min(b1,b2)+1:honey+1]) + sum(honeys[max(b1,b2)+1:honey+1]) - honeys[max(b1,b2)]
        else:
            honeysum = sum(honeys[honey:min(b1,b2)]) + sum(honeys[honey:max(b1,b2)]) - honeys[min(b1,b2)]

        ans = max(ans, honeysum)
    
for i in range(1, N-1):
    calc([0, i, N-1])
print(ans)

그렇게 경우의 수를 줄여 똑같이 연산을 돌려봤더니 55점까진 올랐지만 여전히 통과는 안됐다.

import sys

N = int(sys.stdin.readline())

honeys = list(map(int, sys.stdin.readline().split()))
ans = 0

sums = [0 for i in range(N)]
sums[0] = honeys[0]

for i in range(1, N):
    sums[i] = sums[i-1] + honeys[i]

def calc(l):
    honeysum = 0
    n1, n2, n3 = l[0], l[1], l[2]

    honeysum = max(sums[n3] - honeys[n1] + sums[n3] - sums[n2] - honeys[n2],
                    sums[n2] - honeys[n1] + sums[n3] - sums[n2-1] - honeys[n3],
                    sums[n2] - honeys[n2] + sums[n3] - honeys[n2] - honeys[n3])

    return honeysum

for i in range(1, N-1):
    ans = max(ans, calc([0, i, N-1]))
    
print(ans)

해서 매번 sum연산을 하기보다 누적합 리스트를 만들어둔 뒤 연산을 진행했더니 통과했다.