[백준|파이썬] 14719: 빗물 (골드5)

문제

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

14719번: 빗물

 

 

🐍파이썬

import sys
input=sys.stdin.readline

answer = 0
h, w = map(int, input().split())    #2차원 세로 h, 2차원 가로 w
arr = list(map(int, input().split()))   #블록이 쌓인 높이
for i in range(1, len(arr)-1):
    left_max = max(arr[:i+1])
    right_max = max(arr[i+1:])
    total_min = min(left_max, right_max)
    
    if total_min > arr[i]:
        answer += total_min - arr[i]
        
print(answer)

💡 풀이과정

1. 빗물이 고이려면 블럭 i의 양쪽 블럭의 높이가 i보다 높아야 한다.
2. for루프를 돌면서 각 블럭의 이전 블럭들 중 가장 높은 블럭, 다음 블럭들 중 가장 높은 블럭을 구한다.
3. 이때 빗물은 두 블럭 중 더 작은 높이의 블럭만큼 고일 수 있기 때문에, min(left_max, right_max)에서 현재 블럭의 높이를 빼주어 이번 블럭에서 고일 빗물의 높이를 구해준다. 
4. 첫 번째와 마지막 블럭에는 빗물이 고일 수 없기 때문에 for 루프를 돌 리스트의 범위는 range(1, len(arr)-1) 이다.

 

다른 풀이 방법

_, _ = map(int, input().split())	#h, w가 쓰일 일이 없으므로 변수 할당x
walls = list(map(int, input().split()))

stack = []
answer = 0

for i, h in enumerate(walls):
    while stack and walls[stack[-1]] < h:
        b = walls[stack.pop()]
        if not stack:
            break
        d = i - stack[-1] - 1
        wh = min(walls[stack[-1]], h) - b
        answer += d * wh
    stack.append(i)

print(answer)

👇 풀이방법 참고 블로그

https://kimmeh1.tistory.com/261?category=926574 

[백준 14719] 빗물