[백준_14719] 빗물_python

https://www.acmicpc.net/problem/14719

14719번: 빗물

문제

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

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

입력

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

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

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

출력

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

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

 

문제해결

블록의 높이가 입력으로 주어지고 블록안에 고이는 빗물의 총량을 출력하는 문제이다.

단순 구현문제이지만 구현하기위한 식을 유도하는과정에서 고민한 문제였다.

양쪽끝은 제외하여 1부터 w-1(가로:w)까지의 위치를 탐색을 하며 해당위치의 왼쪽max, 오른쪽max값을 찾은 후

왼쪽과 오른쪽값의 min값과 현재위치의 블록높이의 차가 해당위치에서의 고이는 빗물의 양이 된다.

 

행과 열 둘 중 어느기준으로 문제를 해결해야할까 고민을 했던 문제였다.

 

h , w = map(int,input().split())
block = list(map(int,input().split()))
answer = []
for i in range(1,w-1):
    left = max(block[:i])
    right = max(block[i+1:])
    real = min(left,right)
    rain = real - block[i]
    if rain > 0:
        answer.append(rain)
print(sum(answer))