[구현][백준, 14719] 빗물

입력예제

반례가 될 수 있는 케이스를 담은 입력 예제입니다.

4 7
3 0 3 4 1 2 1

 

 

 

 

문제 풀이

문제 풀이는 총 두 단계로 나뉩니다.

1. 물이 고일 수 있는 범위 탐색

 - 0번 인덱스부터 오른쪽으로 이동하며,

(1) 자신보다 크거나 같은 레벨을 갖는 최초 인덱스를 찾습니다. (0번 ~ 2번, 2번~3번)

(2) (1)에 해당하는 것이 없다면, 오른쪽에 있는 인덱스의 레벨 중 가장 큰 값을 가지는 인덱스를 찾습니다(3~5번, 5~6번)

 

2. 탐색된 범위 내에 고인 물의 양 계산

1번 단계를 통해 찾아진 범위 안에 속하는 물의 양을 계산합니다.

계산 방법은 왼쪽 기둥과 오른쪽 기둥 중, 낮은 기둥을 기준으로 정하고, 물의 양을 계산합니다.

0번~2번 -> 기준: 3 / 답: 3

2번~3번 -> 기준: 3 / 답: 0

3번~5번 -> 기준: 2 / 답: 3

5번~6번 -> 기준: 1 / 답: 0

 

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def find_range(sIdx):
    secIdx = sIdx + 1
    for i in range(sIdx + 1, w):
        if heights[sIdx] <= heights[i]:  # sIdx와 같은 레벨이거나 큰 레벨 탐색
            return i
        if heights[secIdx] < heights[i]:  # sIdx 보다 낮은 레벨 중 가장 큰 레벨 탐색
            secIdx = i
    return secIdx


def calculate_amount_water(sIdx, eIdx):
    horizon = min(heights[sIdx], heights[eIdx])
    cnt = 0
    for i in range(sIdx+1, eIdx):
        cnt += (horizon - heights[i])
    return cnt


if __name__ == "__main__":
    h, w = map(int, input().split())  # h: 세로  w: 가로
    heights = list(map(int, input().split()))
    tot_amount_water = 0
    sIdx = 0
    while sIdx < w - 1:
        eIdx = find_range(sIdx)
        # print(sIdx, eIdx)
        # print(calculate_amount_water(sIdx, eIdx))
        tot_amount_water += calculate_amount_water(sIdx, eIdx)
        sIdx = eIdx
    print(tot_amount_water)