[BOJ/Python] 14719. 빗물

📌 문제

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

14719번: 빗물

 

📌 문제 접근 방법

1. 우선 블록들 중에서 가장 높이가 높은 블록을 찾는다.
2. 그 블록을 기준으로 왼쪽과 오른쪽으로 나눠서 탐색한다.
   이하 가장 높이가 높은 블록을 기준 블록, 0번 부터 기준 블록의 왼쪽인덱스까지를 왼쪽 그룹, 
   기준 블록의 오른쪽인덱스부터 마지막 인덱스까지를 오른쪽 그룹이라 칭하겠다.
3. 기준 블록의 왼쪽 인덱스부터 시작하여 0번 인덱스까지 왼쪽 그룹에서 가장 높이가 큰 블록을 찾는다.
   여기서 찾은 블록과 기준 블록 사이의 블록들은 빗물이 고일 수 있다.
4. 빗물이 고이는 블록들은 (3에서 찾은 블록의 높이 - 자신의 높이) 만큼 빗물이 고이므로, 이를 result에 저장한다.
5. 3에서 찾은 블록을 기준 블록으로 왼쪽으로 계속 탐색해 나간다. 기준 블록이 0이 되면 탐색을 멈춘다.
6. 오른쪽 그룹도 마찬가지로 진행한다. 기준 블록이 W-1이 되면 탐색을 멈춘다.

 

📌 코드

# 백준 14719 빗물

def left(idx):
    global result

    if idx == 0:
        return
    
    temp = blocks[:idx]
    high = max(temp)
    for i in range(idx-1, -1, -1):
        if blocks[i] == high:
            for j in range(i+1, idx):
                result += high - blocks[j]
            left(i)
            return


def right(idx):
    global result

    if idx == W-1:
        return
    
    temp = blocks[idx+1:]
    high = max(temp)
    for i in range(idx+1, W):
        if blocks[i] == high:
            for j in range(idx+1, i):
                result += high - blocks[j]
            right(i)
            return


H, W = map(int, input().split())
blocks = list(map(int, input().split()))

result = 0
for i in range(W):
    if blocks[i] == max(blocks):
        # 인덱스, 높이
        left(i)
        right(i)
        break

print(result)