[BOJ: 21758] - Python / 파이썬 - 꿀 따기

o_jooon_·2024년 1월 30일

algorithm boj python

BOJ

목록 보기

20/49

서론

그리디, 누적 합 문제입니다.
최대한 꿀을 많이 따기 위해선 벌이 최소 하나는 왼쪽 또는 오른쪽 끝에 있어야 합니다.
따라서, 최대가 되는 경우의 수는 세 가지 중 하나입니다.

벌 하나가 가장 왼쪽, 꿀통이 가장 오른쪽, 나머지 벌이 중간 어딘가
벌 하나가 가장 오른쪽, 꿀통이 가장 왼쪽, 나머지 벌이 중간 어딘가
벌이 모두 양쪽 끝, 꿀통이 중간 어딘가

누적합을 통해 세 가지 경우의 수 중 가장 큰 수를 빠르게 찾고 출력하면 되는 문제입니다.
1번 경우의 수만 고려하여 풀다가 2, 3번 경우의 수를 까먹고 계속 풀리지 않아
다른 분의 풀이 방식을 참고하여 알아냈습니다.

난이도

골드 5

문제

조건

시간 제한	메모리 제한
1 초	512 MB

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

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

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

두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$ 의 꿀을 따서, 전체 꿀의 양은 54가 된다.

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

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

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

입력

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

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

출력

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

제한

$3 \le N \le 100~000$
각 장소의 꿀의 양은 $1$ 이상 $10~000$ 이하의 정수이다.

서브테스크

번호	배점	제한
1	11	$N \le 20$
2	13	$N \le 500$
3	31	$N \le 5~000$
4	45	추가적인 제한이 없음.

예시

예제 입력 1

7
9 9 4 1 4 9 9

예제 출력 1

예제 입력 2

7
4 4 9 1 9 4 4

예제 출력 2

예제 입력 3

3
2 5 4

예제 출력 3

풀이

꿀을 가장 많이 얻기 위해서는 벌 한마리와 꿀통이 가장 멀리 떨어져 있거나, 벌 두마리 사이에 꿀통이 있어야 한다.

누적합을 구한다.
양쪽 끝을 제외한 중간 지점을 탐색한다. (양쪽 끝은 항상 벌 또는 꿀통이 있다.)
벌과 꿀통이 양쪽 끝에 있는 경우와 벌이 양쪽 끝, 꿀통이 중간에 있는 경우를 계산한다.
e.g)
🐝 - 벌, 🍯 - 꿀, 🪣 - 꿀통
🐝🍯🍯🍯🪣(right), 🪣🍯🍯🍯🐝(left) 이 두가지의 경우, 나머지 벌 하나는 중간 어딘가에 있다.
🐝🍯🪣🍯🐝(mid) 이 경우, 꿀통이 중간 어딘가에 있다.

코드

n = int(input())
honey = list(map(int, input().split()))
p_sum = [honey[0]] + [0] * (n - 1)	# 누적합
ans = 0								# 꿀

for i in range(1, n):				# 누적합 초기화
    p_sum[i] = p_sum[i - 1] + honey[i]

for i in range(1, n - 1):			# 변수 명은 꿀통 기준, 양 쪽 끝을 제외한 중간 탐색
	# 꿀 통이 오른쪽 끝, 벌이 왼쪽 끝과 중간 어딘가에 있는 경우
    # i = 중간 어딘가에 있는 벌의 위치
    # 왼쪽 벌 -> 꿀통 = 꿀통까지의 누적합 - 자기 자신 - 중간 벌 = p_sum[-1] - honey[0] - honey[i]
    # 중간 벌 -> 꿀통 = 자기 자신부터 꿀통까지의 부분합(자신 제외) = p_sum[-1] - p_sum[i]
    right = 2 * p_sum[-1] - honey[0] - honey[i] - p_sum[i]
    
    # 꿀 통이 왼쪽 끝, 벌이 오른쪽 끝과 중간 어딘가에 있는 경우
    # i = 중간 어딘가에 있는 벌의 위치
    # 오른쪽 벌 -> 꿀통 = 꿀통까지의 누적합 - 자기 자신 - 중간 벌 = p_sum[-1] - honey[-1] - honey[i]
    # 중간 벌 -> 꿀통 = 자기 자신 직전 까지의 누적합 = p_sum[i - 1]
    left = p_sum[-1] - honey[-1] - honey[i] + p_sum[i - 1]
    
    # 꿀 통이 중간, 벌이 양쪽 끝에 있는 경우
    # i = 중간 어딘가에 있는 꿀통의 위치
    # 왼쪽 벌 -> 꿀통 = 꿀통까지의 누적합 - 자기 자신 = p_sum[i] - honey[0]
    # 오른쪽 벌 -> 꿀통 = 꿀통부터 자신까지의 부분합 - 자기 자신 = p_sum[-1] - p_sum[i - 1] - honey[-1]
    mid = p_sum[i] - honey[0] + p_sum[-1] - p_sum[i - 1] - honey[-1]
    ans = max(ans, right, left, mid)

print(ans)