백준 14719번 - 빗물

빗물 문제 바로 가기

풀이 날짜: 2026-01-31

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

h,w = map(int, input().split())
block = list(map(int, input().split()))
answer = 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]:
        answer += m - block[i]
print(answer)
    

문제 핵심

이 문제의 핵심은 어떤 칸에 고일 수 있는 물의 높이는 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 더 낮은 쪽이라는 점이다. 물은 높은 벽이 있어도 반대쪽이 낮으면 그 높이를 넘을 수 없기 때문에, 항상 min(left, right)가 기준이 된다.

한 칸씩 계산하기

전체를 한 번에 계산하지 않고, 각 위치를 하나의 칸으로 보고 계산한다. 현재 위치 기준으로 왼쪽의 최대 높이와 오른쪽의 최대 높이를 구한 뒤, 그중 낮은 값에서 현재 블록 높이를 빼면 해당 칸에 고이는 물의 양을 알 수 있다.

가장자리를 제외하는 이유

맨 왼쪽과 맨 오른쪽 칸은 한쪽에 벽이 없기 때문에 물이 고일 수 없다. 그래서 반복문은 1부터 w-2까지만 순회하며, 실제로 물이 고일 수 있는 위치만 계산하도록 범위를 제한한다.

물의 양 누적하기

현재 칸의 블록 높이가 물이 찰 수 있는 높이보다 낮을 때만 물이 고인다. 이때 (min(left, right) - block[i]) 값을 전체 합에 더해가며, 모든 칸을 확인한 뒤 최종적으로 고인 빗물의 총량을 구한다.