[백준] 14719. 빗물 - Python

[Gold V]

 

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

14719번: 빗물

 

풀이

아이디어를 생각해내기가 조금 어렵지만, 그것만 생각해낸다면 쉽게 풀이할 수 있는 문제.

 

모든 열에 대하여, 그 칸의 왼쪽과 오른쪽 열의 최댓값을 구하고, (line 7, 8)

왼쪽과 오른쪽의 최댓값 중 더 작은 것에서 현재 열의 칸 수를 빼면 받을 수 있는 빗물의 양이 된다. (line 9)

 

AC.

H, W = map(int, input().split())

blocks = list(map(int, input().split()))

result = 0
for i in range(1, len(blocks)-1):
    left = max(blocks[:i])
    right = max(blocks[i:])
    
    rainAmount = min(left, right) - blocks[i]
    if rainAmount > 0:
        result += rainAmount

print(result)