백준 14719번 파이썬 | 빗물

문제

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

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

입력

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

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

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

출력

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

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

---

풀이

이 문제는 이전 게시글인 창고 다각형과 매우 유사하다. NHN 코딩테스트 대비해서 관련 문제를 풀어보았다.

핵심은 가장 큰 높이의 높이와 인덱스를 찾고 왼쪽에서부터 탑까지, 오른쪽에서부터 탑까지 꾸준히 더해준다.

예시 1번을 보자면 , 가장 큰 높이는 4고 인덱스는 3번째 꺼이다. 그러므로 0번째부터 3번째까지 작아지지 않는 큰수들 3 3 3 4 를 더해준다.

여기까지가 창고 다각형 문제이고 여기에 빗물이 고인부분을 빼려면 각 높이의 합만 빼주면 된다.

그러면 작아지는 부분들과의 차이가 된다. ( 3 + 3 + 3 + 4 - 2 - 1 = 5)

# 14719
# 빗물

import sys
input = sys.stdin.readline

maxH = 1
maxL = 0

H, W = map(int, input().strip().split())

pillar = list(map(int, input().strip().split()))
for i in range(len(pillar)):
    if maxH < pillar[i]:
        maxH = pillar[i]
        maxIndex = i

total = 0
temp = 0
for i in range(maxIndex + 1):
    if pillar[i] > temp:
        temp = pillar[i]
    total += temp
temp = 0
for i in range(W - 1, maxIndex, -1):
    if pillar[i] > temp:
        temp = pillar[i]
    total += temp
print(total - sum(pillar))