(Python3) - 백준(BOJ) 21758 : 꿀 따기

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

누적합 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

전체 칸 수 n과 각 칸의 꿀 양 honey를 선언 후 입력받습니다.

📔 풀이과정

왼쪽부터 i까지 꿀을 채취했을 때 누적량을 계산해서 최댓값을 반환하는 함수 max_honey를 구현해줍니다.

n이 10만이므로 단순 brute force로 두 마리의 벌과 벌통을 삼차원 for loop로 계산하면 시간초과입니다. 따라서 O(n)또는 O(nlogn)의 시간복잡도를 가진 알고리즘으로 해결해야 함을 알 수 있습니다.

 

벌통과 꿀벌의 배치를 보시면 3가지 경우가 있음을 알 수 있습니다.

1. 가장 왼쪽에 벌통이 있는경우

마지막 위치에 꿀벌 한 마리가 있는 것이 가장 많은 꿀을 채취할 수 있습니다.

 

2. 가장 오른쪽에 벌통이 있는 경우

첫 번째 위치에 꿀벌 한 마리가 있는 것이 가장 많은 꿀을 채취할 수 있습니다.

 

3. 벌통이 중간에 있는 경우

최대한 끝에 양쪽 벌이 위치해 있는 것이 가장 많은 꿀을 채취할 수 있습니다.

 

1번과 2번 경우에는 고정되지 않은 벌의 위치를 조정하며 O(n)의 시간복잡도로 누적합을 응용해 정답을 구할 수 있습니다.

3번의 경우에는 고정되지 않은 벌통의 위치를 조정하며 마찬가지로 O(n)의 시간복잡도로 정답을 구할 수 있습니다.

 

1번 경우에 위치를 그림으로 나타내면 다음처럼 나타낼 수 있습니다.

|0(벌통)| ... | i(벌) | ...  | n-1(벌)|

n-1번째 벌은 0번 부터 n-2부터 까지의 꿀을 채취할 수 있습니다. 이는 누적합의 n-2번째 값 - i번째 벌위치의 꿀 양이며 O(1)만에 구할 수 있습니다.

i번째 벌은 0번부터 i-1번까지의 꿀을 채취할 수 있습니다. 이는 누적합의 i-1번째 값이며 마찬가지로 O(1)만에 구할 수 있습니다.

따라서 이 경우의 정답은 두 벌이 채취한 꿀양을 더해 ${max(누적합[n-2] - 꿀[i] + 누적합[i-1])}$ 이 됩니다.

 

2번 경우에 위치를 그림으로 나타내면 다음처럼 나타낼 수 있습니다.

|0(벌)| ... | i(벌) | ...  | n-1(벌통)|

0번 벌은 1번째부터 n-1까지의 꿀을 채취할 수 있습니다. 이는 누적합 n-1번째 값에서 - i번째 벌 위치의 꿀 양 - 0번 칸의 꿀 양입니다.

i번 벌은 i+1부터 n-1까지의 꿀을 채취할 수 있습니다. 이는 누적합 n-1번째 값에서 - 누적합 i번째 값입니다.

따라서 이 경우의 정답은 두 벌이 채취한 꿀양을 더해 ${max(누적합[n-1] - 꿀[i] - 꿀[0] + 누적합[i-1] + 누적합[n-1] - 누적합[i])}$ 가 됩니다.

 

3번 경우에 위치를 그림으로 나타내면 다음처럼 나타낼 수 있습니다.

|0(벌)| ... | i(벌통) | ... | n-1(벌)|

0번 벌은 1번째부터 i-1까지의 꿀을 채취할 수 있습니다. 이는 누적합 i번째 값 - 0번 칸의 꿀 양 입니다.

n-1번 벌은 i번째부터 n-2까지의 꿀을 채취할 수 있습니다. 이는 누적합 (n-1)번째값 - 누적합 (i-1)번째 값 - (n-1)번째 꿀 양입니다.

따라서 이 경우의 정답은 두 벌이 채취한 꿀양을 더해 ${max(누적합[i] - 꿀[0] + 누적합[n-1] - 누적합[i-1] - 꿀[n-1])}$ 이 됩니다.

각 경우에 따른 값을 for loop를 수행해 각자의 최댓값을 저장하고 이 3경우의 최댓값을 반환하는 max_honey를 구현해줍니다.

📔 정답 출력 | 반환

max_honey함수의 결과를 반환합니다.

---

📕 Code

📔 Python3

import sys
input = sys.stdin.readline

def max_honey(n, honey):
    accumulated_honey = [0] * n
    
    for i in range(n):
        accumulated_honey[i] = accumulated_honey[i-1] + honey[i]
        
    # 벌통 왼쪽 벌 두 마리 오른쪽        
    max_honey_case1 = 0
    for i in range(1, n-1):
        max_honey_case1 = max(max_honey_case1, accumulated_honey[n-1] - honey[i] - honey[-1] + accumulated_honey[i-1])
    
    # 벌통 오른쪽 벌 두 마리 왼쪽
    max_honey_case2 = 0
    for i in range(1, n-1):
        max_honey_case2 = max(max_honey_case2, accumulated_honey[n-1] - honey[i] - honey[0] + accumulated_honey[n-1] - accumulated_honey[i])
        
    max_honey_case3 = 0
    for i in range(1, n-1):
        left_sum = accumulated_honey[i] - honey[0]
        right_sum = accumulated_honey[-1] - accumulated_honey[i-1] - honey[-1]
        max_honey_case3 = max(max_honey_case3, left_sum + right_sum)
    return max(max_honey_case1, max_honey_case2, max_honey_case3)

n = int(input())
honey = list(map(int, input().split()))

print(max_honey(n, honey))

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.