꿀 따기 (21758번) - 백준 (BOJ)

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

21758번: 꿀 따기

 

 

 

백준 - 꿀 따기 (21758번)

 

난이도 : Gold 5

알고리즘&자료구조 : Prefix Sum (누적 합)

시간복잡도 : O( N )

 

 

from itertools import accumulate


if __name__ == '__main__':
    N = int(input())
    honey = list(accumulate(map(int, input().split())))
    rmaxy = max((honey[-1] - honey[0]) - (honey[i] - honey[i-1]) + (honey[-1] - honey[i]) for i in range(1, N-1))
    lmaxy = max(honey[-2] - (honey[i] - honey[i-1]) + honey[i-1] for i in range(1, N-1))
    cmaxy = max((honey[-2] - honey[0]) + (honey[i] - honey[i-1]) for i in range(1, N-1))
    print(max(rmaxy, cmaxy, lmaxy))

 

 

누적 합 (Prefix Sum) 을 활용해서 풀 수 있는 문제였다.

 

---

 

▷ itertools 의 accumulate 모듈을 통해, 누적 합 리스트를 만든다.

 

 

① 벌 ~ 벌 ~ 벌통

 

벌 하나는 왼쪽 끝, 벌통은 오른쪽 끝에 고정시키는 것이, 최대로 꿀 빨 수 있는 경우이다.

나머지 벌 하나를 ( 1 ~ N-2 ) 인덱스에 차례대로 위치시키면서

최대로 딴 꿀의 양을 구한다.

 

 

② 벌통 ~ 벌 ~ 벌

 

벌통은 왼쪽 끝, 벌 하나는 오른쪽 끝에 고정시키는 것이, 최대로 꿀 빨 수 있는 경우이다.

나머지 벌 하나를 ( 1 ~ N-2 ) 인덱스에 차례대로 위치시키면서

최대로 딴 꿀의 양을 구한다.

 

 

③ 벌 ~ 벌통 ~ 벌

 

두 벌들이 각각 양쪽 끝에 있는 것이, 최대로 꿀 빨 수 있는 경우이다.

두 벌을 양쪽 끝에 고정시키고, 벌통을 ( 1 ~ N-2 ) 인덱스에 차례대로 위치시키면서

최대로 딴 꿀의 양을 구한다.

 

 

▷ 위의 ① ② ③ 에서 구한 최대 꿀의 양 중에서도,

가장 큰 값을 출력한다.