[백준][Python] 21758번 꿀 따기

21758번: 꿀 따기

 

코드

from copy import deepcopy

n = int(input())
h = list(map(int,input().split()))
sum = deepcopy(h)
ans = 0
for i in range(1,n):
    sum[i] += sum[i-1]

#꿀통이 왼쪽 끝
for i in range(1,n-1):
    ans = max(ans, sum[-2] + sum[i-1] - h[i])

#꿀통이 오른쪽 끝
for i in range(1,n-1):
    ans = max(ans, sum[-1]-h[0] + sum[-1]-sum[i] - h[i])

#벌들이 양쪽 끝
for i in range(1,n-1):
    ans = max(ans, sum[-1]-h[0]-h[-1] + h[i])

print(ans)

 

설명

처음에 먼저 누적합을 다 구해놓고 시작했다. 누적합을 구하기 위해서 일단 copy모듈의 deepcopy()를 사용했다. deepcopy는 깊은 복사로 원본 배열은 유지하고, 다른 곳에 같은 배열을 복사하여 거기서 값을 변경할 수 있게 해준다.

최댓값을 구하기 위해 우리가 생각해야 하는 경우의 수는 총 3가지 이다.

1.  꿀통이 왼쪽 끝에 있는 경우

   이때 벌 한 마리는 반드시 오른쪽 끝에 위치해야 한다. 나머지 한 마리는 for문을 통해 하나씩 비교해가면서 최댓값을     찾는다. 

2. 꿀통이 오른쪽 끝에 있는 경우

    이때 벌 한 마리는 반드시 왼쪽 끝에 위치해야 한다. 나머지 한 마리는 for문을 통해 하나씩 배교해가면서 최댓값을        찾는다.

3. 벌들이 양쪽 끝에 있는 경우

    꿀통의 위치는 벌들 중앙에 있으므로 for문을 통해 비교해가면서 최댓값을 찾는다. 총 값은 모든 값을 더한 값인 sum[-1]에 양쪽 끝 값을 빼고 꿀통 위치인 h[i]값을 한 번 더 더해주면 된다.