https://www.acmicpc.net/problem/21758
공부 날짜 : 2023.01.26
정답 참조 여부 : x
장소별로 꿀의 양이 주어진다.
서로 다른 두 위치에서 벌이 출발하며, 집을 향해가며 각 장소에서 꿀을 수집한다.
이때 벌이 있는 장소에서는 꿀을 수집이 불가능 하며 각 장소에서 꿀을 수집해도 다른 벌은 그 장소에서 같은 양의 벌을 수집 할 수 있다.
이때 벌이 수집할 수 있는 꿀의 최대량을 구하는 문제이다.
상대 위치가 벌벌집, 집벌벌, 벌집벌 3가지 경우로 나누어 생각했다.
벌 집 벌의 경우에 벌은 양끝에 있으며 집은 양끝을 제외한 장소중에서 가장 큰값인 경우 최대값이 된다(집은 2번 수집 되기 때문)
max_sweet = max(data[1:-1])
answer = sum_sweet - data[0] - data[-1] + max_sweet벌 벌 집, 집 벌 벌 의 경우에 양끝에 집과 벌을 두고 나머지 한마리의 위치를 옮겨가며 값을 비교했는데 이때 누적합 알고리즘이 사용되었다.
개인적으로 학창시절 때도 비슷한 개념을 어려워 했다. 경계점을 포함하느냐 제외하느냐, 제외한다면 어디서 값을 참조해야하는가 등이 많이 헷갈려서 어려웠던 문제였다.
소스코드
import sys
input = sys.stdin.readline
########################################
n = int(input())
data = list(map(int, input().split()))
sum_data = [0 for _ in range(n+1)]
sum_sweet = 0
for i in range(1, n+1):
sum_sweet += data[i-1]
sum_data[i] = sum_sweet
# 벌 집 벌 의 형태인 경우
# 양 끝을 제외한 칸중에 가장 큰 값
max_sweet = max(data[1:-1])
answer = sum_sweet - data[0] - data[-1] + max_sweet
# 벌 벌 집 의 경우
# 집 벌 벌 의 경우
for i in range(2, n):
bee_bee_house = sum_sweet - data[0] - data[i-1] + sum_sweet - sum_data[i]
house_bee_bee = sum_sweet - data[-1] - data[i-1] + sum_data[i-1]
answer = answer if answer > bee_bee_house else bee_bee_house
answer = answer if answer > house_bee_bee else house_bee_bee
print(answer)