[알고리즘] BOJ 꿀 따기 21758 #Python

[BOJ] 21758 꿀 따기 바로가기

📍 문제

아래와 같이 좌우로 $N$개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 $9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 $4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 $57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

---

📍 입력

첫 번째 줄에 장소의 수 $N$이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

---

📍 출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

---

📍 풀이

📌 문제 풀이

해당 문제의 케이스를 크게 3가지로 구분할 수 있다.

1. $N$개의 장소 중 가장 왼쪽에 🍯(벌통) 이 존재하고 벌통을 기준으로 오른쪽에 🐝(벌)이 존재하는 경우

2. $N$개의 장소 중 가장 오른쪽에 🍯(벌통) 이 존재하고 벌통을 기준으로 왼쪽에 🐝(벌)이 존재하는 경우

3. $N$개의 장소 중 가장 왼쪽과 오른쪽에 🐝(벌)이 존재하고 🐝(벌) 사이에 🍯(벌통)이 존재하는 경우

---

$case 1$의 초기 상태는 아래 그림과 같다.

벌이 가장 많이 딸 수 있는 꿀의 양을 구하는 방법은 왼쪽에 존재하는 벌의 위치는 고정시키고, 오른쪽에 존재하는 벌의 위치를 오른쪽으로 한칸씩 이동하면서 딸 수 있는 꿀의 양을 계산하는 것이다.

초기 상태에서 왼쪽 벌이 딸 수 있는 꿀의 양은 4 + 1 + 4 + 9 + 9 = 27, 오른쪽 벌이 딸 수 있는 꿀의 양은 4 + 1 + 4 + 9 + 9 = 27 로 총 54 이다.

다음은 오른쪽 벌의 위치를 오른쪽으로 한칸 이동한 경우이다.

왼쪽 벌이 딸 수 있는 꿀의 양은 9 + 1 + 4 + 9 + 9 = 32, 오른쪽 벌이 딸 수 있는 꿀의 양은 1 + 4 + 9 + 9 = 23 으로 총 55 이다.

오른쪽 벌이 한칸 이동하면서 생긴 변화는 오른쪽 벌이 도착한 장소의 꿀(4)을 2마리의 벌 모두가 딸 수 없게 되고, 오른쪽 벌이 존재하던 곳의 꿀(9) 을 왼쪽 벌이 딸 수 있게 된 것이다.

정리해보자면, 현재 딸 수 있는 꿀의 양 = 기존에 딸 수 있는 꿀의 양 - 오른쪽 벌이 도착한 장소의 꿀 * 2 + 오른쪽 벌이 존재하던 곳의 꿀 와 같다는 것을 알 수 있다.

이를 코드로 작성하면 아래와 같다.

value = 2 * (total - (arr[0] + arr[1])) # 현재 딸 수 있는 꿀의 양

for i in range(2,N): # i : 
	# 현재 딸 수 있는 꿀의 양 = 기존에 딸 수 있는 꿀의 양 + 오른쪽 벌이 존재하던 곳의 꿀 - 오른쪽 벌이 도착한 장소의 꿀 * 2 
    value += (arr[i-1] - arr[i]*2)
    # 최대값 갱신
    answer = max(answer, value)

위 방법을 모든 $case$에 적용하여 문제를 해결한다.

✍ 코드

from sys import stdin

def solution(N, arr):

    answer = 0
    total = sum(arr)
    
    # case1 : B B H
    value = 2 * (total - (arr[0] + arr[1]))
    answer = max(answer, value)
    for i in range(2,N):
        value += (arr[i-1] - arr[i]*2)
        answer = max(answer, value)

    # case2 : H B B
    value = 2 * (total - (arr[-1] + arr[-2]))
    answer = max(answer, value)
    for i in range(N-2, 1, -1):
        value += (arr[i] - arr[i-1]*2)
        answer = max(answer, value)

    # case3 : B H B
    value = arr[1] + total - (arr[0] + arr[-1])
    answer = max(answer, value)
    for i in range(2, N-2):
        value += (arr[i] - arr[i-1])
        answer = max(answer, value)

    return answer

# input
N = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))

# result
result = solution(N, arr)
print(result)