[백준/ 파이썬] 21758번 꿀 따기

백준 21758번 꿀 따기

백준 21758번 꿀 따기 문제를 파이썬으로 풀어봤습니다.
이 문제는 크게 벌통을 기준으로 3가지의 경우를 고려해서 문제를 풀어주면 됩니다.

Case #1 🌸🐝🐝 <벌통이 좌측 끝에 위치할 때>
이 경우 벌 하나는 우측에 고정되었을때 가장 최대이고, 나머지 벌은 벌통에 가깝게 이동하면서 최대의 경우를 찾아주면 됩니다.

Case #2 🐝🐝🌸 <우측 끝에 벌통이 위치할 떄>
이 경우 벌 하나의 위치는 맨 좌측에 고정됬을때 최대이고, 나머지 벌은 좌측에서 벌통 직전까지 이동하면서 그 중에서 최대인 경우를 구해주면 됩니다.

Case #3 🐝🌸🐝 <좌/우측 끝에 벌들이 위치하고 그 사이에 벌통이 위치할떄>
벌들 사이에 벌통이 위치한 경우. 벌들의 위치는 좌/우 양 끝에 고정이 됩니다.
따라서 이때는 벌통의 위치를 옮겨가면서 가장 최대인 경우를 구해주면 됩니다.

! 이 문제를 처음에 풀었을때는 55점이 나왔습니다. 무엇이 문제인지 잘 모르겠어서 다른 분들의 내용을 참고해보니까 누적합을 미리 구해서 시간을 아껴야 했습니다. 누적합을 쓰고 제출을 했더니 100점이 나왔습니다.

Case #1 🌸🐝🐝

def caseOne():
max_sum = 0
for i in range(n-2, 0, -1):
#total은 얻을 수 있는 꿀의 누적 합.
#(total[-1] - honey[n-1] - honey[i]) 우측 벌의 총 합
#(total[i]-honey[i]) 이동하는 벌의 총 합
temp = (total[-1] - honey[n-1] - honey[i]) + (total[i]-honey[i])
max_sum = max(max_sum, temp)
return max_sum

Case #2 🐝🐝🌸

def caseTwo():
max_sum = 0
for i in range(1, n-1):

    # total은 얻을 수 있는 꿀의 누적 합.
    #(total[-1] - honey[0] - honey[i]) 좌측 벌의 총 합
    #(total[-1] - total[i]) 이동하는 벌의 총 합
    temp = (total[-1] - honey[0] - honey[i]) + (total[-1] - total[i])
    max_sum = max(max_sum, temp)
return max_sum

Case #3 🐝🌸🐝

def caseThree():
max_sum = 0
for i in range(1, n-1):

    # total은 얻을 수 있는 꿀의 누적 합.
    #(total[i] - honey[0]) 좌측 벌의 총 합
    #(total[-1]-total[i-1]-honey[-1]) 우측 벌의 총 합
    temp = (total[i] - honey[0]) + (total[-1]-total[i-1]-honey[-1])
    max_sum = max(max_sum, temp)
return max_sum

전체 코드

import sys
input = sys.stdin.readline

# Case 1. 벌통 꿀벌 꿀벌
def caseOne():
    max_sum = 0
    for i in range(n-2, 0, -1):
        #total은 얻을 수 있는 꿀의 누적 합.
        #(total[-1] - honey[n-1] - honey[i]) 우측 벌의 총 합
        #(total[i]-honey[i]) 이동하는 벌의 총 합
        temp = (total[-1] - honey[n-1] - honey[i]) + (total[i]-honey[i])
        max_sum = max(max_sum, temp)
    return max_sum
# Case 2. 꿀벌 꿀벌 벌통
def caseTwo():
    max_sum = 0
    for i in range(1, n-1):
        # total은 얻을 수 있는 꿀의 누적 합.
        #(total[-1] - honey[0] - honey[i]) 좌측 벌의 총 합
        #(total[-1] - total[i]) 이동하는 벌의 총 합
        temp = (total[-1] - honey[0] - honey[i]) + (total[-1] - total[i])
        max_sum = max(max_sum, temp)
    return max_sum
#Case 3. 꿀벌 벌통 꿀벌
def caseThree():
    max_sum = 0
    for i in range(1, n-1):
        # total은 얻을 수 있는 꿀의 누적 합.
        #(total[i] - honey[0]) 좌측 벌의 총 합
        #(total[-1]-total[i-1]-honey[-1]) 우측 벌의 총 합
        temp = (total[i] - honey[0]) + (total[-1]-total[i-1]-honey[-1])
        max_sum = max(max_sum, temp)
    return max_sum

n = int(input())
honey = list(int(x) for x in input().split())
total = [] #꿀의 누적 합
total.append(honey[0])
for i in range(1, n):
    total.append(total[i-1]+honey[i])

res = max(caseOne(), caseTwo(), caseThree())
print(res)