첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고이지 않을 경우 0을 출력하여라.
입력 예시
4 4
3 0 1 4
출력 예시
5
풀이
빗물이 고이는 조건은 좌우로 골짜기가 생길 때이다. 우리는 골짜기를 높이가 내림차순으로 이루어지다가 오름차순으로 이루어지는 구간 으로 정의해 볼 수 있겠다. 이 때 골짜기는 양 끝단의 높이 중 최솟값을 기준으로 채워지게 된다.
즉 우리는 더 이상의 골짜기가 생기지 않을 때까지 전체 칸을 반복하며 탐색하는 코드를 짜볼 수 있다.
풀이 코드
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
block_list = list(map(int, input().split()))
def valley_fill(left, right) :
result = 0
min_h = min(block_list[left], block_list[right])
for i in range(left, right+1) :
if block_list[i] < min_h :
result += min_h - block_list[i]
block_list[i] = min_h
return result
def find_valleys() :
result = 0
top = -1
disc = True
for i in range(1, W) :
if block_list[i-1] > block_list[i] :
top = i-1
break
for j in range(i+1, W) :
if block_list[j-1] > block_list[j] and not disc :
result += valley_fill(top, j-1)
top = j-1
disc = True
elif block_list[j-1] < block_list[j] and disc :
disc = False
if not disc :
result += valley_fill(top, W-1)
return result
answer = 0
while True :
tmp = find_valleys()
if not tmp :
break
answer += tmp
print(answer)
