[백준] 14719 빗물 - 파이썬

 

문제

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

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

입력

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

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

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

출력

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

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

 

 

 

 

 

풀이

 

 

시뮬레이션 문제이다.

 

특정위치를 기준으로 물이 고이는지를 판단하면 되기 때문에 for문을 돌리면 간단히 해결 가능하다.

 

이제 맨처음 벽과 마지막 벽에는 물이 고일 수 없기 때문에 for(i,M-1)로 벽의 맨 처음과 마지막은 제외하고 for문을 돌린다.

 

특정 위치에 물이 고이기 위해선 자신보다 더 높은 블록으로 왼쪽과 오른쪽이 둘러싸여 있어야한다.

 

그러므로 i 의 현재 위치를 기준으로 왼쪽에서 가장 큰 벽과 오른쪽에서 가장 큰 벽을 찾는다.

 

두 벽중에 더 작은 벽이 곧 빗물의 양이 된다 ( 그래야지 빗물이 안넘침)

 

ex) 현재 위치가 1인 벽 양옆에 3과 4인 벽이 있다면 3-1인 2의 빗물이 고이게됨