[백준] 빗물 (Gold 5) Python 풀이

 

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

14719번: 빗물

 

풀이

"물은 어디에 고이는가?"에 대해 고민해 봐야 한다. 물은 움푹 패인 곳에 고인다. 움푹 패였다는 것은, 양 옆의 지형이 현재 위치의 지형보다 높게 형성되었다는 것이다. 즉, 이러한 조건을 만족할 때 물이 고인다고 할 수 있다.

그리고 "물은 얼마큼 고이는가?"에 대해서도 고민해 봐야 한다. 예를 들어 현재 위치가 3이고, 왼쪽에서 가장 높은 2번 위치의 높이가 4이고, 오른쪽에서 가장 높은 5번 위치의 높이가 6이라고 하자. 그러면 물은 2번 위치와 4번 위치 중에서 높이가 더 낮은 2번 위치만큼 차게 될 것이다.

 

따라서 다음과 같은 과정으로 이 문제를 풀 수 있다.

1. 왼쪽 끝부터 오른쪽 끝까지 순차적으로 주변 지형의 높이를 확인한다. 이때 현재 기준 왼쪽의 최대 높이, 현재 기준 오른쪽의 최대 높이를 저장한다.

2. 이렇게 저장한 왼쪽 최대 높이, 오른쪽 최대 높이가 모두 현재 위치의 지형보다 높아야 물이 고인다. 이처럼 물이 고이는 조건이 성립한다면 물이 쌓이는 양을 누적해준다.

 

Python 코드로 살펴보면 다음과 같다.

# 백준 14719 빗물
h, w = map(int, input().split())
arr = list(map(int, input().split()))

# 고이는 빗물의 총량 구하기
area = 0

# 첫째 칸과 마지막 칸은 물이 고일 수 없으니 1~w-1의 범위만 순회한다.
for i in range(1, w-1):

    left_h = max(arr[:i]) # 왼쪽 최대 높이
    right_h = max(arr[i+1:]) # 오른쪽 최대 높이

    # 왼쪽이나 오른쪽 기둥이 현재 위치보다 높아야 물이 고일 것이므로, 
    # 왼쪽이나 오른쪽의 최소 높이가  현재 기둥보다 높아야 물이 고인다.
    # 최소 높이 - 현재 기둥 높이 만큼 물이 찬다.
    if min(left_h, right_h) > arr[i]: 
        area += min(left_h, right_h) - arr[i]

print(area)