[백준] 21758. 꿀 따기

 

📌문제

21758번: 꿀 따기

 

🎖️난이도

 

✔️풀이

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

# 누적합 구해놓기
nujuck = [honey[0]]
for i in range(1, n):
    nujuck.append(nujuck[-1]+honey[i])
    
total = 0
# 1. 통"벌"벌 => [0][1~n-2][-1]
for i in range(1, n-1):
    total = max(total, nujuck[n-2]-honey[i]+nujuck[i-1])
    
# 2. 벌"벌"통 => [0][1~n-2][-1]
for i in range(1, n-1):
    total = max(total, nujuck[-1]-honey[0]-honey[i]+nujuck[-1]-nujuck[i])
    
# 3. 벌"통"벌 => [0][1~n-2][-1]
for i in range(1, n-1):
    total = max(total, nujuck[i]-honey[0]+nujuck[-1]-nujuck[i-1]-honey[-1])
    
print(total)

 

🧠노트

맨 처음에 뭔가 가장 크게 3가지 경우로 나눠서 풀어야 되나..? 정도까지만 생각하고

도저히 명확하고 100% 모든 경우를 빠짐없이 탐색하면서 최대값을 구하는 알고리즘이 안떠올라서

다른 풀이들을 참고해서 다시 풀었다...!

 

핵심은,

1. 벌통의 위치에 따라 3가지 경우로 크게 나누어서 구하는 것 (이에 따라 첫번째 꿀벌의 위치도 pix 할 수 있음)
2. 누적합을 미리 구해놔서 각 case마다의 완전탐색 시의 덧셈(누적합) 연산 횟수를 줄이기

이다.

 

벌통과 꿀벌의 위치는 크게

1. 통"벌"벌
2. 벌"벌"통
3. 벌"통"벌

으로 생각해주면 된다.

 

1번과 2번과 같이 양끝으로 벌통의 위치가 정해지면

첫번째 꿀벌의 위치는 완전 반대편으로 위치하는 것이 최대이고,

 

3번과 같이 벌통이 꿀벌의 사이에 위치하는 경우에는

두 꿀벌의 위치는 맨 앞과 맨 끝으로 위치하는 것이 최대이다.

 

🔍참고

-