문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

풀이

오랜만의 구현문제라 신난다. 예) 3 1 2 3 4 1 1 2

풀이방법 > 왼쪽부터 큰값을 하나 잡아 오른쪽을 봤을 때 같거나 높은 곳이 있다면 그 사이의 값은 처음의 큰값으로 채워지게 된다.

오른쪽부터도 똑같이 진행한다.

빗물이 받아졌을 때의 결과는 3 3 3 3 4 2 2 2 이다 결과값은 이 값을 뺀 차이 합이다.

import sys
sys.stdin = open('input.txt')

H,W = map(int,input().split())
original_graph = list(map(int,input().split()))
graph = original_graph[::]
# 5 2 4 1 3 5 3 4


i = 0
big = i # 왼쪽부터 시작하는데 큰값을 자기로 잡고
while i<W: # 오른쪽에 위치한 값중 나보다 큰 곳 & 같은 곳이 있다면
    if graph[i]>= graph[big]:
        for j in range(big,i):  # 그 사이의 값을 모두 큰 값으로 바꿔준다
            graph[j] = graph[big]
        big = i                 # 이제 큰 값을 그 뒤부터가 된다.
    i += 1


k = W-1     # 뒤에서부터 시작하겠다
big2 = k
while k>=big:
    if graph[k]>= graph[big2]:  # 똑같이 왼쪽의 값이 큰 값보다 크거나 같다면
        for j in range(big2,k,-1):      # 바꿔준다.
            graph[j] = graph[big2]
        big2 = k
    k -= 1

result =0
for i in range(W):      # 바꿔준 값들의 차이가 빗물양
    result += graph[i]-original_graph[i]
print(result)