[lv3] 21758. 꿀 따기(Python 파이썬 풀이)

출처

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

21758번: 꿀 따기

결과

문제

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

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

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

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

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

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

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

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

입력

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

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

출력

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

제한

• 3≤N≤100 000
• 각 장소의 꿀의 양은 1 이상 10 000 이하의 정수이다.

예제 입력 1

7
9 9 4 1 4 9 9
0

예제 출력 1

57

예제 입력 2

7
4 4 9 1 9 4 4

예제 출력 2

54

예제 입력 3

3
2 5 4

예제 출력 3

10

해석

벌통의 위치를 1. 벌들 사이에 둘 때와 2. 벌들 옆에 둘 때로 생각해서 풀어야 한다.

1. 벌들 사이에 벌통을 두는 경우
   벌통을 중간에 두고 벌들의 위치를 각각 왼쪽과 오른쪽방향 아무데나 둘 수 있는 경우를 생각해보자. 벌들의 위치는 벌통을 기준으로 왼쪽과 오른쪽 아무데나 한 곳씩 둘 수 있으므로, 벌이 왼쪽과 오른쪽 가장자리에 있는 경우가 꿀을 많이 딸 수 있는 위치가 될 것이다. 왼쪽 벌은 이제 0번째를 제외하고 1번째 꿀부터 시작하여 벌통이 있는 위치까지 꿀을 따갈 것이고, 오른쪽 벌도 n-1번째(인덱스 값)을 제외하고 n-2번째 꿀부터 벌통위치까지에 있는 모든 꿀들을 담아 갈 것이다. 즉, 1번째부터 n-1번째 꿀들을 다 담고, 벌통 위치에 있는 꿀만 두번 중복하기 때문에 꿀을 최대한 담기 위해서는 벌통의 위치를 꿀이 가장 많았던 위치에 두면 된다.
2. 벌통의 위치가 벌들 사이가 아닌 경우
   이 경우는 (벌), (벌), (벌통) 혹은 (벌통), (벌), (벌)인 경우를 말한다. 예시로 벌통이 벌들보다 오른쪽에 있는 경우를 생각해보자. 벌 1마리는 왼쪽 가장자리, 벌통은 중간위치가 아닌 반대쪽 가장자리에 둬야 최대 조건을 만족시킬 수 있다. 이제, 남은 벌 1마리를 어디에 둘 것이냐에 따라 결과가 달라진다. 벌통을 오른쪽 가장자리에 뒀기 때문에 남은 벌 한마리는 자신의 위치로부터 오른쪽 끝까지 꿀들을 따갈 것이다. 그런데 자신의 위치에 있던 벌의 양은 0이 된다. 그러므로 또 다른 벌 또한 그만큼 손해를 보게 된다. 손해를 최소화 해주는 위치를 찾아야 한다. for 구문을 통해서 벌의 위치를 1번째 부터 n-2위치까지 이동시키면서 2마리가 손해보는 양이 최소가 되는 구간의 꿀의 양을 구하면 된다.
   벌통을 왼쪽에 두었을 때도 이와 마찬가지로 for구문을 통하여 벌이 n-2위치부터 1번째 위치까지 이동시키면서 손해가 최소가 되도록 구하면 됩니다.
   코드에서 구한 left와 벌 한마리가 가장자리 왼쪽에서부터 n까지 모든 꿀의 양을 합한 것이고, right는 반대로 오른쪽에서 계산했을 때의 값입니다.

이제 1번과 2번의 결과들 중에서 최소값을 출력해주면 됩니다.

소스 코드

import sys
sys.stdin = open("21758in.txt", 'r')
 
n = int(sys.stdin.readline().strip())
honey = list(map(int, sys.stdin.readline().strip().split()))
li = []
ans = 0
# 벌통을 가운데에 뒀을 때
a = sum(honey[1 : n-1]) + max(honey[1 : n-1])
# 벌통을 왼쪽에 뒀을 때
left = l_total = sum(honey[1:n])
l_max = r_max = 0
for i in range(1, n-1):
    l_total -= 2 * honey[i]
    if l_max < l_total:
        l_max = l_total
    l_total += honey[i]
# 벌통을 오른쪽에 뒀을 때
right = r_total = sum(honey[0:n-1])
for i in range(n-2, -1, -1):
    r_total -= 2 * honey[i]
    if r_max < r_total:
        r_max = r_total
    r_total += honey[i]
print(max(a, l_max + left, r_max + right))