BOJ-14719 빗물

https://www.acmicpc.net/problem/14719

문제 소개

2차원 세계에 쌓여있는 블록의 정보가 주어진다. 비가 충분히 왔을 때 고이는 빗물의 총량을 구한다.

문제 풀이

i번째 블록의 높이를 arr[i]라고 해 보자.

i번째 블록 위로 고이는 빗물의 양을 알기 위해서는 i의 이전과 이후 구간 각각에서 블록의 높이 최대값이 필요하다.

먼저 아래의 두 정보가 필요하다.

1. i 이전 블록 중 최대 높이인 블록

2. i 이후 블록 중 최대 높이인 블록

그 다음으로 1번과 2번 중 높이가 낮은 블록의 높이를 t라고 했을 때, i번째 블록 위로 고이는 빗물의 양은 t - arr[i]가 된다.

t를 코드로 나타내면 아래와 같다.

t = min(max(arr[:i]), max(arr[i + 1:]))

빗물이 고이기 위해서는 t가 arr[i]보다 높아야 한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

h, w = map(int, input().split())
arr = list(map(int, input().split()))

acc = 0
for i in range(1, w - 1):
    # t 계산
    t = min(max(arr[:i]), max(arr[i + 1:]))
    # 빗물이 고일 수 있는 경우에만 값을 누적
    if t > arr[i]:
        acc += t - arr[i]

print(acc)