[알고리즘] 빗물의 총량 계산, brute force, python (1)

[백준 알고리즘] 14719번 - 빗물의 총량 계산하는 문제. brute force를 사용. 언어는 python

 

[문제]

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

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

 

[조건]

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

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

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

 

[풀이]

핵심 : 더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다. 

• 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다
• 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다
• 그중 더 낮은 건물의 높이를 구한다
• 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다
• 그 값이 현재 인덱스에서 담길 수 있는 빗물의 양

def trapping_rain(buildings):
    raindrop = 0
    for i in range(len(buildings)):
        # 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이        
        max_left = max(buildings[:i+1])
        # 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이 
        max_right = max(buildings[i:])
        # 둘중에 어떤 값이 더 큰가?
        which_low = min(max_left, max_right)
        # 절대값 주의
        raindrop = raindrop + abs(buildings[i] - which_low)
    return raindrop

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
# 10

print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
# 6