[BOJ/Python] 14719_빗물

문제 출처: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

4 4
3 0 1 4

예제 출력 1

5

예제 입력 2

4 8
3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5
0 0 0 2 0

예제 출력 3

0

힌트

힌트 1:

힌트 2:

힌트 3:

 

---

풀이

 

우선 코드는 다음과 같다.

 

import sys
 
h,w = map(int,sys.stdin.readline().split())
h_list = list(map(int,sys.stdin.readline().split()))
 
higest = h_list.index(max(h_list))
 
high = h_list[0]
idx = 0
result = 0
sum = 0
for i in range(1,higest+1):
    if h_list[i]>=high:
        result += high * (i-idx-1) - sum
        sum = 0
        idx = i
        high = h_list[i]
    else:
        sum+=h_list[i]
 
high = h_list[-1]
idx = -1
sum = 0
for i in range(2,w-higest+1):
    if h_list[-i]>=high:
        result += high * (idx+i-1) - sum
        sum = 0
        idx = -i
        high = h_list[-i]
    else:
        sum+=h_list[-i]
 
print(result)

제일 높은 높이를 기준으로 좌우를 나누어 탐색하였다.

왼쪽 부분에 고이는 빗물의 총량을 구하는 방법은 다음과 같다.

1. 우선 제일 높은 높이의 index를 구하여 higest에 저장한다.
2. high에 0번째 index의 높이를 넣고, idx=0으로 초기화한다.
3. index 1부터 higest까지 반복문을 이용하여 높이 비교를 한다.
4. 만약 high보다 현재 index의 높이가 더 높다면 high만큼의 빗물이 둘 사이 간격만큼(i-idx-1) 고여있음을 의미한다.
5. 하지만, 둘 사이에 high보다 낮은 높이의 값들이 있다면, 이를 빼주어야 하므로 sum에 낮은 높이의 블록들의 합을 저장하여 이만큼을 빼준 값이 최종적으로 고여있는 빗물의 양이 된다.
6. high에 현재 index의 높이를 저장하고, sum을 초기화하고, idx에 현재 index를 넣는다.
7. 이 과정을 higest (제일 높은 높이의 index) 까지 수행한다.

오른쪽 부분에 고이는 빗물의 총량을 구하는 방법도 위와 같다.

Python의 음수 인덱스를 이용하여 -1부터 제일 높은 높이까지 위의 과정을 수행한다.

 

최종적으로 오른쪽 부분에 고이는 빗물에 총량까지 구하고 나면 이를 출력한다.