[파이썬] 백준 #14791 빗물

이번 주의 챌린지 문제. 시간을 들여 고민하니 간단한 규칙을 찾을 수 있었다.

---

문제

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

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

입력

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

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

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

4 4
3 0 1 4

출력

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

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

5

---

풀이 과정

처음에는 양쪽 끝을 기준으로 잡고 생각했었는데, 문제를 풀면 풀수록 반례가 떠올라서 다른 방법으로 접근하였다.

1. 입력값 설정하기

H, W = map(int, input().split())
arr = list(map(int, input().split()))
rainism = 0

입력값을 차례로 받고, 출력할 변수 rainism을 설정했다.

2. 조건 설정하기

# (1)
i = 0
start = 0
while i < W:
    if arr[i] >= arr[start]:
        for j in range(start, i):
            rainism += arr[start] - arr[j]
        start = i
    i += 1

# (2)
i = W-1
end = W-1
while i >= 0:
    if arr[i] > arr[end]:
        for j in range(end, i, -1):
            rainism += arr[end] - arr[j]
        end = i
    i += -1

입력값은 숫자로만 구성된 리스트이다. 이 형태를 활용하여 규칙을 찾으려고 노력했다.
빗물이 쌓이는 규칙은 보다 높은 블럭이 양쪽에 존재할 때이다.
이는 리스트에서 보면 index를 기준으로 보다 작은 값이 등장하고, 이후 보다 크거나 같은 값이 등장할 때, 빗물이 쌓이는 것이다.

이에 따라 (1) 문단을 작성하였다.
start를 기준으로 arr[i]가 크거나 같다면, 그 범위 내에서 arr[start] - arr[j] 만큼의 빗물이 생긴다.
그러나 이 규칙만으로는 반례가 발생한다.
start가 가장 높은 블록이라면 쌓이는 빗물을 계산할 수 없기 때문이다.

이를 보완해주기 위해 (2) 문단을 작성하였다.
이번에는 end에서부터 같은 계산을 하는 대신, arr[end]와 arr[i]가 같은 조건은 배제하였다.

- 답안

# 입력값 설정
H, W = map(int, input().split())
arr = list(map(int, input().split()))
rainism = 0

# 왼쪽부터 오른쪽으로, start보다 숫자가 크거나 같은 지점이 나올 때 arr[start] - arr[j]만큼 더함.
i = 0
start = 0
while i < W:
   if arr[i] >= arr[start]:
       for j in range(start, i):
           rainism += arr[start] - arr[j]
       start = i
   i += 1

# 오른쪽부터 왼쪽으로, end보다 숫자가 큰 지점이 나올 때 arr[end] - arr[j]만큼 더함.
i = W-1
end = W-1
while i >= 0:
   if arr[i] > arr[end]:
       for j in range(end, i, -1):
           rainism += arr[end] - arr[j]
       end = i
   i += -1

print(rainism)

---

*모든 문제의 저작권은 백준 온라인 저지(https://www.acmicpc.net/) 원작자에게 있습니다.
백준 14719번(https://www.acmicpc.net/problem/14719)