[백준 21758] 꿀 따기 (Python)

2022. 8. 31. 11:01

문제 링크 #

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

문제 해설 #

Idea #

벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외
벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함

Data Size #

N: 3 <= int <= 100,000
arr[i]: 1 <= int <= 10,000

해설 코드 #

python

N = int(input())
arr = list(map(int, input().split()))
forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]]
for i in range(1,N):
    forward[i] = forward[i-1] + arr[i]
    backward[N-i-1] = backward[N-i] + arr[N-i-1]
answer = 0

for i in range(1,N-1):
    answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2)
    answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2)
    answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1])

print(answer)