문제
https://www.acmicpc.net/problem/14719
코드
h, w = map(int, input().split())
arr = list(map(int, input().split()))
left = [0]*w
left[0] = arr[0]
right = [0]*w
right[-1] = arr[-1]
for i in range(1, w):
left[i] = max(left[i-1], arr[i])
for i in range(w-2, -1, -1):
right[i] = max(right[i+1], arr[i])
answer = 0
for i in range(1, w-1):
if min(left[i], right[i])-arr[i] > 0:
answer += min(left[i], right[i])-arr[i]
print(answer)풀이
dp로 풀이했습니다
left 배열의 i인덱스에는 i인덱스 보다 왼쪽에 있는 블록중 가장 큰 값이 들어가고 right 배열은 반대로 오른쪽에 있는 블록중 가장 큰 값이 들어가요
그 다음 arr을 순회하면서 left[i] 와 right[i] 중 작은 값으로 계산해줬습니다![]
