[Python] 백준 14719 빗물

1. 문제 링크

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

14719번: 빗물

---

2. 문제 요약

• 아래 그림과 같이 빗물의 총량을 구하기

---

3. 아이디어 정리

투 포인터를 이용하여 빗물 총량을 구한다. ⇒ 오른쪽 포인터 최댓값, 왼쪽 포인터 최댓값을 이용해서 빼준다

1. 오른쪽 포인터 최대값이 큰 경우, 왼쪽 빗물 구하기 & 왼쪽 이동
2. 왼쪽 포인터 최대값이 큰 경우, 오른쪽 빗물 구하기 & 오른쪽 이동

• 예시를 통한 로직 순서

---

4. 문제 풀이

4-1. 내 풀이

import sys

h, w = map(int, sys.stdin.readline().split())  # 세로, 가로
arr = list(map(int, sys.stdin.readline().split())) # 블록 높이

left = 0
right = w - 1

max_left = arr[left]
max_right = arr[w - 1]

result = 0

# 투포인터
while left < right:
    max_left = max(max_left, arr[left])
    max_right = max(max_right, arr[right])
    # 1. 오른쪽 포인터 최대값이 큰 경우, 왼쪽 빗물 구하기 & 왼쪽 이동
    if max_right >= max_left:
        result += max_left - arr[left]
        left += 1
    else:
    # 2. 왼쪽 포인터 최대값이 큰 경우, 오른쪽 빗물 구하기 & 오른쪽 이동
        result += max_right - arr[right]
        right -= 1

print(result)

 

---

5. 결론

• 기존 투포인터와 약간 다른 방식 ⇒ 최댓값을 계속 기록하면서 그 수만큼 빼주는 방식