백준 14719번: 빗물 python 풀이 및 정답 코드

문제 링크

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

14719번: 빗물

 

 

문제 설명

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

 

문제 풀이

이 문제도 스택이다.

1. 스택에 현재 보는 인덱스를 넣어주고
2. 블럭 높이가 높아지는 걸 찾아서 고인 물을 더해준다.

 

 

코드

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
block = list(map(int, input().split()))
stack = []
answer = 0

for i in range(w):
    while stack and block[i] > block[stack[-1]]:
        top = stack.pop()
        if not stack:
            break
        distance = (i - stack[-1]) - 1
        height = min(block[i], block[stack[-1]]) - block[top]
        answer += (distance * height)
    stack.append(i)

print(answer)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰