[백준/파이썬] #14719

풀이를 봤는데 생각보다 간단한 문제였다... 30분 타임어택으로 못 풀어서 오늘도 풀이를 참고한 다음 풀어봤다. 

 

빗물이 고이는 원리를 생각하면 되는 문제였다. 내 왼쪽의 블럭들 중 가장 높은 지점(left_max)과 내 오른쪽의 블럭들 중 가장 높은 지점(right_max)을 구한 다음, 빗물은 낮은 곳에만 고일 수 있으니 둘의 최솟값을 구해준다. 

 

그러면 적어도 내가 있는 위치 i 에서는 그 값의 차이(min_max - arr[i])만큼은 물이 고일 것이다. 

H, W = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0

for i in range(1, W-1):
    left_max = max(arr[:i])
    right_max = max(arr[i+1:])
    min_max = min(left_max, right_max)
    if min_max > arr[i]:
        answer += min_max - arr[i]

print(answer)