백준 21758 - 꿀 따기 (파이썬)

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

풀이

누적합 배열을 사용하며, 벌과 꿀통의 배치를 최적화하여 최대 꿀 수확량을 계산하는 문제이다.

먼저 누적합 계산을 위해서 초기화를 진행한다.

psum = [0] * N
for i in range(N):
    if i == 0:
        psum[i] = A[i]
    else:
        psum[i] = psum[i - 1] + A[i]

1. 첫번째 경우 (벌이 양 끝, 꿀통이 중간한 가정)
   • 첫번째 벌은 0번 위치 (A[0])
   • 두번째 벌은 N - 1번 위치 (A[N - 1])
   • 꿀통은 중간에 있는 최대 꿀량의 벌통
     1. max(A[1:-1]) → (첫 번째와 마지막을 제외한 부분에서 최댓값)
2. answer = psum[N - 2] - psum[0] + max(A[1:-1])
3. 두번째 경우 (벌 - 벌 - 꿀통 가정)
   • 첫 번째 벌: A[0] (맨 왼쪽)
   • 두 번째 벌: A[i] (중간)
   • 꿀통: A[N-1] (맨 오른쪽)
   a = psum[N - 1] - psum[0] - A[i]
   • 첫 번째 벌이 벌통 A[0]에서 출발하여 끝까지 가면서 얻는 꿀.
   • 단, A[i]에 도착하면 그 벌이 꿀을 가져가지 않음.
   b = psum[N - 1] - psum[i]
   • 두 번째 벌이 A[i]에서 시작하여 끝까지 가면서 얻는 꿀.
4. for i in range(1, N - 1): a = psum[N - 1] - psum[0] - A[i] b = psum[N - 1] - psum[i] answer = max(answer, a + b)
5. 세번째 경우 (꿀통 - 벌 - 벌 가정)
   • 꿀통: A[0] (맨 왼쪽)
   • 첫 번째 벌: A[i] (중간)
   • 두 번째 벌: A[N-1] (맨 오른쪽)
   꿀 수확량
   • 두 번째 벌이 A[N-1]에서 출발하여 A[i]까지 가면서 얻는 꿀.
   • A[i]는 벌이 꿀을 먹지 못함.
   b = psum[i - 1]
   • 첫 번째 벌이 A[0]에서 A[i]까지 가면서 얻는 꿀.
6. a = psum[N - 2] - A[i]
7. for i in range(1, N - 1): a = psum[N - 2] - A[i] b = psum[i - 1] answer = max(answer, a + b)

시간 복잡도 분석

1. 누적합 계산 : O(N)
2. 각 경우 반복문 : O(N)
3. 총 시간 복잡도 : O(N)

코드

# 백준 21758 - 꿀 따기
# 분류 : 그리디, 누적합

N = int(input())
A = list(map(int, input().split()))

psum = [0] * N
for i in range(N) :
    if i == 0 :
        psum[i] = A[i]
    else :
        psum[i] = psum[i - 1] + A[i]

answer = psum[N - 2] - psum[0] + max(A[1:-1])

for i in range(1, N - 1) :
    a = psum[N - 1] - psum[0] - A[i]
    b = psum[N - 1] - psum[i]
    answer = max(answer, a + b)

for i in range(1, N - 1) :
    a = psum[N - 2] - A[i]
    b = psum[i - 1]
    answer = max(answer, a + b)

print(answer)