[백준] 빗물

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

14719번: 빗물

 

쉽게 생각했을 때, 해당 열에 고인 빗물의 양은 해당 열을 기준으로 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 가장 작은 길이 - 해당 열의 블록의 길이이다. (단, >= 0)

 

leftMaxRainwater[i] = 0 ~ i열로 이동할 때 가장 긴 블록의 길이

rightMaxRainwater[i] = W-1 ~ i열로 이동할 때 가장 긴 블록의 길이

를 구한 뒤 min(leftMaxRainwater[i-1], rightMaxRainwater[i+1]) - rainwater[i] (1< i < W-1) 가 양수라면 answer 에 더하여 반환한다.

 

import sys

H, W = map(int, sys.stdin.readline().split())
rainwater = list(map(int, sys.stdin.readline().split()))
answer = 0
leftMaxRainwater = [0] * W
rightMaxRainwater = [0] * W

for i in range(W):
    leftMaxRainwater[i] = max(leftMaxRainwater[i-1], rainwater[i]) if i - 1 >= 0 else rainwater[0]
    rightMaxRainwater[W-1-i] = max(rightMaxRainwater[W-i], rainwater[W-1-i]) if W-i < W else rainwater[-1] 

for i in range(1, W-1):
    value = min(leftMaxRainwater[i-1], rightMaxRainwater[i+1]) - rainwater[i]
    answer += value if value > 0 else 0
    
print(answer)