(Python/🥇5) 백준알고리즘 14719번: 빗물

문제 출처: https://www.acmicpc.net/problem/14719

14719번: 빗물

풀이:

 

import sys


H, W = map(int,input().split(" ")) # H 가로 W 세로


res = 0
for i in range(1, W - 1): # 첫째 칸과 마지막 칸은 물이 안 고임
    left_max = max(lst[:i])
    right_max = max(lst[i+1:])
    min_num = min(left_max, right_max)

    # 빗물 고이는 곳이 양 옆으로 높은곳이 있으면 물이 잠긴다. 그럼 그 작은 높이의 벽돌과 내 벽돌 차이만큼 물이 찬다.
    if lst[i] < min_num:
        res += min_num - lst[i]

print(res)

 

처음에는 블록이 쌓인곳을 다 1로 만드려고 maps 를 만들어서 하려고 했지만 잘 되지 않아서

물이 쌓이는 원리를 생각했다. 따로 알고리즘을 필요없고 0과 W 는 첫칸과 마지막칸이니깐 배제해준다

 

1번에 물이 쌓이는 양은 1번 전후로 최댓값 벽돌을 찾아주고 그 둘중에 작은 값 만큼 쌓을수 있다.

 

 

left_max , right_max 를 구해주고 작은 값인 min_num 에 넣어준다

min_num 보다 작아야지 채울수 있으므로 

작을때 min_num(작은벽돌) 에서 나를 빼주면 그 칸에서 채울수 있는 물의 양이 나온다.