꿀 따기 (백준 21759번)

문제

아래와 같이 좌우로 N$N$개의 장소가 있다.

https://upload.acmicpc.net/7eac9e04-f000-482d-9ad5-05cc2363df05/-/preview/

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

https://upload.acmicpc.net/8ca82402-c379-40cd-902d-9ecc24c35d1f/-/preview/

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4+1+4+9+9=27$4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

https://upload.acmicpc.net/a9794fde-7a1b-4c4d-82b5-f1b8e7daaa73/-/preview/

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9+4+4+9+9=35$9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4+9+9=22$4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 57$57$이 된다.

https://upload.acmicpc.net/5b264635-fc6b-498a-af76-bbe08197ab32/-/preview/

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 N$N$이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

나의 풀이

import sys
input=sys.stdin.readline

N=int(input().strip())
honey=list(map(int,input().strip().split()))
sum_honey=[]
sum_honey.append(honey[0])
for i in range(1,N):
    sum_honey.append(sum_honey[i-1]+honey[i])
answer=0
#왼쪽에 벌통
for i in range(1,N-1):
    answer=max(answer, sum_honey[N-2]+sum_honey[i-1]-honey[i])
#오른쪽에 벌통
for i in range(1,N-1):
    answer=max(answer,sum_honey[N-1]-honey[0]+sum_honey[N-1]-sum_honey[i]-honey[i])
#가운데 벌통
m_max=max(honey[1:N-1])
answer=max(answer,sum_honey[N-1]-honey[0]-honey[-1]+m_max)
print(answer)

• 3가지 경우를 생각해야 한다. 벌통이 오른쪽 끝, 왼쪽 끝, 가운데 끝에 존재할 때의 각각 최대 값을 찾아 비교한다.
• 가운데 벌통의 경우 벌통이 있는 곳은 2번 꿀을 딸 수 있기 때문에, 가운데 중 최대값을 찾아주면 해결된다.