백준 21758 파이썬 코드

import sys

n = int(sys.stdin.readline().rstrip())
my_list = list(map(int, sys.stdin.readline().split()))
s = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    s[i] = s[i - 1] + my_list[i - 1]
answer = 0

for k in range(2, n):
    temp = (s[k] - s[1]) + (s[-2] - s[k - 1])
    answer = max(answer, temp)

for k in range(2, n):
    temp = (s[-2] - s[k]) + 2 * (s[k - 1] - s[0])
    answer = max(answer, temp)

for k in range(2, n):
    temp = (s[k - 1] - s[1] + 2 * (s[-1] - s[k]))
    answer = max(answer, temp)

print(answer)

회고

처음에는 누적합 + 투 포인터 개념으로 접근을 해보려고 했었다. 그런데 투 포인터로 접근했을 때, 어떤 결과에 대한 방향성 설정을 할 수 없다는 것을 깨달았다. 즉, 투 포인터로 접근이 안되고 브루트포스로 접근해야하는데 이 경우에는 O(N^2)으로 TLE가 발생할 수 밖에 없다는 것을 알았다.

따라서, 시간 복잡도를 O(N) 수준으로 줄여야 하는데 가능한 방법은 그리디 알고리즘 밖에 없어보였다. 또한, 그리디 알고리즘을 세 가지 경우를 나눠서 적용해야 하는 것으로 분류했다.

꿀<벌벌, 벌>꿀<벌, 벌벌<꿀 인 경우가 있을 것이다. 이 세가지 경우에 대해서 그리디 알고리즘을 적용했다. 당연한 얘기지만 벌들이 이동할 수 있는 거리는 항상 큰 것이 좋다. 즉, 꿀<벌벌일 경우 꿀과 벌 하나의 좌표는 고정된다. 그리고 나머지 벌 한 마리가 어디에 위치하면 좋을지에 대해 선형적으로 탐색했다.

세 가지 경우에 대해서 선형 탐색으로 했으므로 시간 복잡도는 O(3*N)으로 확인되었다.

 

추가적으로 필요한 부분

누적합을 할 때는 계산의 편의성을 위해 0번 배열을 하나 추가한 후, 누적합을 구해주는 것이 좋다.