[BOJ14719 - Python] 빗물

문제

---

14719번: 빗물

고이는 빗물의 총량 구하기

 

 

풀이

---

1. 가장 왼쪽 블록부터 시작

 

2. 맨 위쪽 블록부터 맨 아래쪽 블록까지 아래의 수행을 차례대로 진행한다.

2-1. 현재 보고 있는 위치보다 높거나 높이가 같은 블록을 마주쳤을 때, 두 블록 사이에 들어가 있는 공간 개수만큼 고인 물을 저장하는 변수에 더한다.

2-2. 만약 블록을 마주치지 않았다면 두 블록 사이에 고인 물이 없다는 것이므로 더하지 않는다.

 

3-1. 한 열에 대하여 해당 수행을 완료했을 때, 마주쳤던 블록들 중 가장 멀었던 블록에서 2번을 다시 수행한다.

3-2. 만약 블록을 마주치지 않았다면 바로 다음 열에서 수행한다.

 

→ 2차원 세계의 끝까지 도달할 때까지 반복한다.

 

* 코드

import sys

H, W = map(int, sys.stdin.readline().split())
world = list(map(int, sys.stdin.readline().split()))

well = 0  # 고인 물
next_i = 0
for i in range(len(world) - 1):
    h = world[i]
    if h != 0:
        for water_h in range(1, h + 1):
            for j in range(i + 1, len(world)):
                now_h = world[j]
                if now_h >= water_h:
                    well += j - i - 1
                    next_i = max(next_i, j)
                    break
    i = next_i

print(well)

 

고민쓰의 흔적쓰