[백준/누적합] 21758번 : 꿀 따기

- 문제 : https://www.acmicpc.net/problem/21758

 

이 문제는 케이스 분류 + 누적합으로 푸는 문제다. 먼저 누적합을 구하는 원리를 알아야 하는데, 아래 그림을 참고하면 된다. 여기서 sum_arr[i] 는 0 ~ i 인덱스까지의 합을 의미한다. 

 

특정 구간의 누적합 구하기

 

정답 풀이

누적합

원소의 합을 빠르게 구해야하므로 기존 배열의 값의 누적합을 sum_arr 이름의 배열에 저장한다.

 

케이스 분류

벌집 1개와 벌 2마리를 1차원 배열에 위치시킨 뒤 벌 2개가 벌집에 가는 길에 있는 원소의 최대 합을 누적합으로 구한다. 이 경우에는 벌벌꿀, 꿀벌벌, 벌꿀벌 총 3가지 케이스를 나누어서 진행하면된다. 모든 케이스는 ABC 형식인데, A는 0 인덱스, C는 (n - 1) 인덱스에 있고, B의 위치만 i로 for문으로 변경시키면서 최댓값을 구하는 로직이다. 

 

1. 벌벌꿀

이 경우에는 벌 하나가 0 인덱스, 벌집이 (n - 1) 인덱스에 있고, 벌이 for 문으로 i 인덱스(1 ~ n - 1)에 있다. 벌은 벌이 있는 곳을 지나갈 수 없으므로 움직일 수 있는 범위는 [1, n - 1]이다. 

 

 

0 인덱스의 벌을 bee1, i 인덱스의 벌을 bee2라고 하자.

- bee1은 [1, i - 1], [i + 1, n - 1]까지의 원소 합(bee2가 있는 i 번째는 빼야 한다) -> sum_arr[n - 1] - sum_arr[0] - arr[i] 

- bee2는  bee2는 [i + 1, n - 1]까지의 원소 합 -> sum_arr[n - 1] - sum_arr[i]

 

2. 꿀벌벌

이 경우에는 벌집이 0 인덱스, 벌 하나가 (n -1) 인덱스에 있고, 벌이 for 문으로 i 인덱스(1 ~ n - 2)에 있다. 벌은 벌이 있는 곳을 지나갈 수 없으므로 움직일 수 있는 범위는 [0, n - 2]이다. 

 

 

(n - 1) 인덱스의 벌을 bee1, i 인덱스의 벌을 bee2라고 하자.

- bee1은 [0, i - 1], [i + 1, n - 2]까지의 원소 합(bee2가 있는 i 번째는 빼야 한다) -> sum_arr[n - 2]  - arr[i] 

- bee2는  [0, i - 1]까지의 원소 합 -> sum_arr[i -1]

 

3. 벌꿀벌

이 경우에는 벌이 0 인덱스와 (n - 1) 인덱스에 있고, 벌집이 for 문으로 i 인덱스(1 ~ n - 2)에 있다. 

0 인덱스의 벌을 bee1, (n - 1) 인덱스의 벌을 bee2라고 하자.

- bee1은 [1, i]까지의 원소 합 -> sum_arr[i]  - arr[0] 

- bee2는  [i, n - 2]까지의 원소 합 -> sum_arr[n - 2] - sum_arr[i - 1]

 

 

각 케이스에서의 bee1 + bee2 최댓값을 구하고, 그 중에서의 최댓값을 answer에 저장한 뒤 출력하면 된다.

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

answer = 0
sum_arr = [0] * n
sum_arr[0] = arr[0]
for i in range(1, n):
    sum_arr[i] = arr[i] + sum_arr[i - 1]
    
# 벌벌꿀
for i in range(1, n):
    bee1 = sum_arr[n - 1] - sum_arr[0] - arr[i]
    bee2 = sum_arr[n - 1] - sum_arr[i]
    answer = max(answer, bee1 + bee2)
  
# 꿀벌벌
for i in range(1, n - 1):
    bee1 = sum_arr[-2] - arr[i]
    bee2 = sum_arr[i - 1]
    answer = max(answer, bee1 + bee2)

# 벌꿀벌
for i in range(1, n - 1):
    bee1 = sum_arr[i] - sum_arr[0]
    bee2 = sum_arr[n - 2] - sum_arr[i - 1]
    answer = max(answer, bee1 + bee2)
    
    
print(answer)

 

 

 

Reference

https://velog.io/@a87380/21758%EB%B2%88-%EA%BF%80-%EB%94%B0%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC