[백준][Python] 14179번. 빗물 (골드5)

!https://d2gd6pc034wcta.cloudfront.net/tier/11.svg

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

20528

11681

9146

56.875%

문제

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

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14719/1.png

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14719/2.png

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

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1

4 4
3 0 1 4

예제 출력 1

5

예제 입력 2

4 8
3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5
0 0 0 2 0

예제 출력 3

0

힌트

힌트 1:

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14719/ex1.png

힌트 2:

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14719/ex2.png

힌트 3:

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14719/ex3.png

알고리즘 분류

• 구현
• 시뮬레이션

아이디어

구현, 시뮬레이션 문제이므로 로직을 정리해보면,

1. 각 건물에서 왼쪽과 오른쪽으로 가장 높은 건물을 찾기
2. 현재 건물에서 쌓일 수 있는 빗무릐 양은 min(왼쪽 최대, 오른쪽 최대) - 현재
3. 각 건물에 대해 계산 수행

문제 풀이

def calculate_trapped_water(heights):
    if not heights:
        return 0
    
    n = len(heights)
    left_max = [0] * n
    right_max = [0] * n
    trapped_water = 0

    # 왼쪽에서 최대 높이 구하기
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], heights[i])
    
    # 오른쪽에서 최대 높이 구하기
    right_max[n - 1] = heights[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], heights[i])
    
    # 현재 위치에서 쌓일 수 있는 빗물 계산
    for i in range(n):
        trapped_water += min(left_max[i], right_max[i]) - heights[i]
    
    return trapped_water

# 입력 받기
H, W = map(int, input().split())
heights = list(map(int, input().split()))

# 결과 출력
print(calculate_trapped_water(heights))