[백준] [Python] #14719 빗물

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

14719번: 빗물

순간 문제를 보자마자 보이는 2차원 격자무늬 그림에 이거 2차원 배열 써야하나 싶었다.

그러나 그런 문제는 아니었고 숫자를 받아서 배열 생성하는 뻘짓을 안한 것만 해도 감사하다.

 

left_wall = arr[0]
ans = 0
ansList = [0]

for i in range(1, m):
    if arr[i] < left_wall: 
        ans += left_wall-arr[i]
    elif arr[i] >= left_wall:
        left_wall = arr[i]
        ansList.append(ans)
        ans = 0
    print(left_wall, ans, ansList)

print(ansList)
print(sum(ansList))

다양한 뻘짓을 했는데 그나마 다행인건 투포인터 문제인데 포인터 비스무리하게 left_wall 잡고 갔다는 것이다.

투포인터라는 문제가 있는 줄도 모르는데 혼자 머리로 이만큼 했음 잘했지!!

 

import sys
sys.stdin = open('input.txt', 'r')

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

leftIdx = 0
rightIdx = w-1

leftMax = arr[leftIdx]
rightMax = arr[rightIdx]

ans = 0

#투포인터
while leftIdx < rightIdx:
    leftMax = max(leftMax, arr[leftIdx])
    rightMax = max(rightMax, arr[rightIdx])

    #오른쪽 포인터 최대값이 큰 경우, 왼쪽 빗물 구하기 & 왼쪽 이동
    if rightMax > leftMax : 
        ans += leftMax - arr[leftIdx]
        leftIdx += 1
    #왼쪽 포인터 최대값이 큰 경우, 오른쪽 빗물 구하기 & 오른쪽 이동
    else: 
        ans += rightMax - arr[rightIdx]
        rightIdx -= 1

print(ans)

그래서 답은 구글 스승님이 알려줌...

이동하는 인덱스를 계속 업데이트 한다는 것과,

최대값을 비교해서 오른쪽이 크면 왼쪽을 이동하고, 왼쪽이 크면 오른쪽을 이동한다는 것 자체가 새로웠다.

 

 

참고1 : https://ryu-e.tistory.com/41

참고2 : https://namhandong.tistory.com/139