백준_21758_꿀 따기 (python) (맛도리)

# 맛도리 문제였다

# 쉽지 않았다

# 그리디적인 생각 == 직관

# 누적합

 

여러 알고리즘이 결합된 맛있는 문제였다. 쉽지 않았고 중간에 포기할까도 생각했지만 스크롤을 내렸을 때 중등부 1번 문제인 것을 보고 더 생각을 해보기로 했다.

 

일단 주어지는 입력의 최대 크기는 십만이다. 마지막 테스트 케이스를 통과하기 위해서는 이 십만개의 테스트 케이스를 통과해야 한다. 문제를 읽고 단순하게 생각하기만 해 본다면 꿀벌이 위치해야 하는 위치 2곳과 꿀통이 위치해야 하는 위치를 합한 총 3곳을 조합 형태로 뽑아 경우의 수를 구하는 것에서 끝나는게 아니라 여기서 더 나아가 벌들이 위치한 곳에서부터 이동하면서 꿀을 채취해야한다. 더 나아갈 필요도 없이 3곳을 조합 형태로 뽑는 곳에서부터 시간 초과가 발생한다.

 

그렇다면 어떻게 해야할까 여기까지 왔을 때 놓친 것이 뭐가 있을까를 생각해야 한다. 

필자는 여기서 꿀통이 위치했어야 하는 위치가 있지 않을까를 생각했다. 왜냐하면 벌은 꿀통을 향해 날라가기 때문이고 구해야할 것은 최대한 많은 양의 꿀을 채취해야 한다는 것이다. 그렇다면 여기서 꿀통은 두 가지 경우의 수가 생긴다. 가장 맨 왼쪽과 가장 맨 오른쪽에 위치할 수 있게 된다.

 

 여기까지 생각하고 보니 또 두 벌의 위치를 계산해줘야 한다. 하지만 최대 99999(꿀통의 위치는 정했으니)에서 2 곳을 뽑아라? 이미 또 시간 초과다.  여기서 한번 더 생각할 것이 벌 한 마리 또한 가장 맨 오른쪽에 있거나 가장 맨 왼쪽에 있으면 된다. 여기까지 왔으면 남은 벌 한마리의 위치만 반복문을 돌면서 꿀의 양을 계산해주면 된다.

 

하지만 여기에서 예외가 하나 있는데 필자가 짠 코드는 꿀통이 맨 왼쪽과 맨 오른쪽에 있고 꿀이 제일 많은 위치가 어디이든 벌이 그곳을 무조건 지나가기 때문에 상관은 없었지만 입력의 크기가 3일 경우 가운데에 있는 꿀의 양이 최대일 때 예외가 발생한다. 그래서 3일 때는 꿀이 제일 많은 위치에 값을 *2 해주면 된다.

 

# 코드

# 21758 꿀 따기
import sys
input = sys.stdin.readline
n = int(input())
honeys = list(map(int,input().split()))
answer = 0
def left(): # 꿀통이 제일 왼쪽에 있는 경우
    ret = 0
    dp = [0] * n
    for i in range(len(honeys)-2, -1, -1):
        dp[i] = dp[i+1] + honeys[i]
    for i in range(1,len(honeys)-1):
        ret = max(ret, (dp[0] - honeys[i]) + (dp[0] - dp[i]))   
    return ret

def right(): # 꿀통이 제일 오른쪽에 있는 경우
    ret = 0
    dp = [0] * n
    for i in range(1,len(honeys)):
        dp[i] = dp[i-1] + honeys[i]
    for i in range(1,len(honeys)-1):
        ret = max(ret, (dp[-1] - honeys[i]) + (dp[-1] - dp[i]))
    return ret

if n == 3:
    print(max(honeys) * 2)
else:
    answer = max(answer, left())
    answer = max(answer, right())
    print(answer)

 

# 회고 

예외가 있는 코드는 따로 또 작성해야 하고 만약 테스트 케이스에서 주어지지 않았으면 풀지 못했을 수도 있었다. 문제를 해결했다고 생각을 쉽게 하지 말고 놓친 부분이 있지 않을까를 생각해봐야겠다.