아래와 같이 좌우로 개의 장소가 있다.
장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.
두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 의 꿀을 따서, 전체 꿀의 양은 54가 된다.
위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 의 꿀을 따고 오른쪽 장소에서 출발한 벌은 의 꿀을 따므로, 전체 꿀의 양은 이 된다.
위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.
장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.
첫 번째 줄에 장소의 수 이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.
7
9 9 4 1 4 9 9
57
나머지 예제는 생략한다.
import sys
input = sys.stdin.readline
n = int(input().rstrip())
l = list(map(int,input().rstrip().split()))
# 왼쪽에서부터 시작한 접두사 합
left_prefix_sum = [0]
# 오른쪽에서부터 시작한 접두사 합
right_prefix_sum = [0]
sum_value = 0
answer = -int(1e9)
for i in range(n):
sum_value +=l[i]
left_prefix_sum.append(sum_value)
sum_value = 0
for i in range(n-1,-1,-1):
sum_value += l[i]
right_prefix_sum.append(sum_value)
# 벌통이 양 끝에 있는 경우
for i in range(2,n):
a = left_prefix_sum[n] - left_prefix_sum[i]
b = right_prefix_sum[n] - right_prefix_sum[i]
if i ==2:
answer = max(a*2, b*2, answer)
else:
c = left_prefix_sum[i-1] - left_prefix_sum[1]
d = right_prefix_sum[i-1] - right_prefix_sum[1]
answer = max(a*2+c, b*2+d,answer)
# 벌통이 양 끝을 제외한 곳에 있는 경우
for i in range(2,n):
left = left_prefix_sum[i] - left_prefix_sum[1]
right = right_prefix_sum[n-i+1] - right_prefix_sum[1]
answer = max(answer, left+right)
print(answer)
접두사 합
을 구한 뒤 벌통의 위치를 달리해 각각의 구간 합
을 구해주면서 풀면 시간안에 문제를 해결할 수 있다.