[BOJ / Python] 14719 빗물

🔫 문제 : 14719 빗물

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

 

 

🌱 풀이과정

💡 예제

 

 

1️⃣ 맨 앞과 맨 뒤에서는 물이 고일 수 없다. 

2️⃣ 빗물이 고일 조건 : 좌우로 나보다 높은 블록이 존재하면 됨

3️⃣ 고이는 빗물의 양 : 왼쪽과 오른쪽 블록 중 더 낮은 블록 - 현 위치의 값

 

 

 

👩🏻‍💻 전체코드 

import sys
input = sys.stdin.readline

# 입력
H, W = map(int, input().split())
data = list(map(int, input().split()))

# 빗물의 총량
answer = 0

# 맨 앞과 맨 뒤는 빗물이 고일 수 없으므로 1 ~ W-1까지 탐색
for i in range(1, W - 1):
    left = max(data[:i]) # 왼쪽에서 가장 높은 블록
    right = max(data[i+1:]) # 오른쪽에서 가장 높은 블록
    min_w = min(left, right)

    # 빗물이 고일 조건 : 양쪽의 블록이 나보다 높으면 됨
    # 좌우의 존재하는 블록의 최댓값의 최솟값이 현재 블록보다 크다면 빗물이 고인다. 
    if min_w > data[i]:
        answer += min_w - data[i]

print(answer)

 

 

 

😃 결과