[백준] 14719 빗물 / 구현 / Python 골5

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

 

SWEA에서 풀었던 VIEW 문제와 비슷하다고 생각햇음

접근법은 좀 다르지만..

 

결국 아이디어는 다른 블로그를 통해 얻긴 했는데

 

빗물이 고일 수 있는 위치는 1에서 n-2번째 블록이고, for문 범위를 잡는다

현재 i번째 블록에서 좌, 우를 탐색한다

 

좌에서 max인 값과 우 에서 max값을 찾으면

내 블록 위로 고일 수 있는 좌,우 기둥의 max값을 알 수 있음

어차피 빗물은 벽이 아무리 멀리 떨어져있어도, 나보다 높은 좌우 기둥이 있으면 무조건 고임

 

좌,우 기둥 중 min값에 맞춰 빗물이 최대로 고일 수 있음

 

그리고, 그 좌,우 min 값 중 나 자신의 높이를 빼면 내 위치에서 고이는 빗물의 높이를 알 수 있음

 

그러나 좌,우min-나자신 값이 음수이면 빗물이 고일 수 없다는 뜻

그때는 sum에 더하지 않는다

 

i번째 위치에서 각 좌,우 max를 구하고, 그 값의 min을 구해서 자기 높이를 빼는 과정을 그림으로 나타낸 것

 

코드는 아래와 같다

h,w = map(int,input().split())

arr = list(map(int,input().split()))

result=0

leftl=0
rightl=0
rain=0
for i in range(1,w-1):
    left_max = max(arr[:i])
    right_max = max(arr[i+1:])
    height = min(left_max,right_max)
    if height>arr[i]:
        result+=height-arr[i]

print(result)