[알고리즘 일기 - 파이썬] 227. 빗물

문제 227. (2022-03-29)

 

14719번: 빗물

Baekjoon 14719. 빗물

[파이썬(python) - 시뮬레이션]

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

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

 

---

입력

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

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

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

 

---

출력

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

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

 

---

입력 예시

4 4
3 0 1 4

 

---

출력 예시

5

 

---

❧ 정답

🔎 IDEA) 시뮬레이션

맨 처음 문제 접근 방식을 두 가지로 나눠서 생각했다.

방법 1. 양 옆 블록의 높이를 찾아서 양 블록의 사이에 들어갈 빗물의 총량 구하기
✔️ 방법 2. 맨 아래에 칸 부터 채울 수 있는 공간 채우기

[Line 8 - 12]
👉 i : 맨 아래의 1칸부터 빗물을 채울 수 있는 지 체크한다.
👉 j : 가로 칸 한 줄에 빗물이 들어갈 수 있는 지 체크한다.
#10
👉 현재 높이가 블록 높이보다 큰 경우에만 빗물이 들어갈 수 있다.
#11
👉 현재 위치에서 좌측 블럭 높이의 최댓값과 우측 블럭 높이의 최댓값을 구한 뒤, 빗물이 들어갈 수 있는 경우에만 rst값을 1증가 시킨다.