[백준] 14719번 빗물 (python)

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

14719번: 빗물

 

해결 과정은 다음과 같다.

 

1. 주어진 막대 길이들 중, 가장 긴 막대의 인덱스를 찾는다.
2. 가장 긴 막대를 기준으로 오른쪽 그룹과 왼쪽 그룹으로 나누어 탐색한다.
3. 가장 길이가 긴 막대의 인덱스까지 반복문을 돌린다. (오른쪽 그룹은 0에서 해당 인덱스까지, 왼쪽 그룹은 가로길이에서 해당 인덱스까지 역순으로)
4.  오른쪽 그룹 기준으로, 가장 오른쪽 막대의 길이를 변수 right_height로 선언한다.
5. 가장 오른쪽 막대의 길이가 바로 옆 막대의 길이보다 길 경우에는 두 길이의 차를 total_water에 더해준다. 만약 바로 옆 막대의 길이가 더 길 경우, right_height를 옆 막대의 길이로 갱신한다.
6. 왼쪽 역시 똑같이 해준다. 단, 역순이니 인덱스에 주의해야 한다.

 

처음에는 가로길이의 중간을 기준으로 나눌까 했지만 그렇게 되면 빗물의 양을 계산하기가 매우 어렵다;;; 가장 긴 막대를 기준으로 가장자리부터 탐색해야 한 칸씩 계산할 수 있다.

 

정답 코드

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
height = list(map(int, input().split()))
tallest_height = height.index(max(height))

right_total_water = 0
right_height = height[0]
for i in range(tallest_height):
    if right_height > height[i+1]:
        right_total_water += right_height - height[i+1]
    else:
        right_height = height[i+1]

left_total_water = 0
left_height = height[-1]
for i in range(w, tallest_height, -1):
    if left_height > height[i-1]:
        left_total_water += left_height - height[i-1]
    else:
        left_height = height[i-1]

print(right_total_water + left_total_water)