백준 14719번 빗물 | python | 시뮬레이션

문제

링크

풀이

꽤 유명한(흔한) 문제인 빗물 문제다. 가로 방향으로 한 칸씩 이동하면서 현재 세로줄에 물이 몇 블럭 채워질 수 있는지만 생각하면 된다.

풀이방식은 현재 세로줄을 기준으로 왼쪽, 오른쪽을 나눈다. 이후 왼쪽 블럭의 최댓값과 오른쪽 블록의 최댓값을 구하여 이 둘의 최솟값 m을 구한다. 이때 현재 세로줄의 블럭은 m-현재 세로줄의 블럭 만큼 물이 채워질 것이다. 참고로 양 끝은 물이 채워질 수 없으므로 제외하고 진행한다. 사실 글보다 그림으로 보면 단번에 이해될 것이다. 아래 사진과 최종 코드를 확인해보자.

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)

한 2년전쯤? 이 문제를 처음 봤을 땐 물이 쏟아져내리는 것까지(?) 이상하게 생각하느라 이해하는 데 오래 걸렸던 적이 있다 ㅎ 너무 복잡하게 생각하려드는 것도 문제인 것 같다. 최대한 빠르고 간단하게 풀이해야지 라는 마음으로 풀어야겠다.