[백준] 14719번 문제 (빗물) 파이썬(Python) 풀이

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

14719번: 빗물

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
block = list(map(int, input().split()))
result = 0

for i in range(1, w - 1):
    left = max(block[:i])
    right = max(block[i + 1:])
    m = min(left, right)

    if m > block[i]:
        result += m - block[i]

print(result)

이 문제의 핵심은 더 큰 건물들 사이에 껴있으면 물이 잠긴다는 것을 파악하는 것이다.

 

for 문을 반복하며 매번 left와 right에서 가장 큰 값을 구한다.그리고 그 중에서 가장 작은 값(m)을 구한다.만약 m이 현재 블록보다 크다면 현재 블록은 빗물이 잠기는 블록이 된다.

 

따라서, m - 현재블록 높이(block[i])를 result에 더한다.