[구현] 빗물 (14719)

문제 설명

 

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

 

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0 이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라

---

💡 문제 풀이

 

➀ 최대 높이의 인덱스를 찾는다(max_index)

② max_index기준으로 왼쪽영역에서 빗물이 고일 수 있는 영역을 구한다.

➂ max_index기준으로 오른쪽에서 빗물이 고일 수 있는 영역을 구한다.

➃ (②+➂+최대 높이)에서 입력으로 주어진 모든 높이의 합을 뺀다.

 

import sys
input = sys.stdin.readline
h,w = map(int, input().split())
info = list(map(int, input().split()))

max_index = info.index(max(info)) #1 최대높이 인덱스
total,temp = 0,0

#2 왼쪽영역~최대높이까지의 합
for i in range(max_index+1):
  if info[i] > temp:
    temp = info[i]
  total += temp

#3 오른쪽영역
temp = 0
for i in range(w-1, max_index, -1):
  if info[i]>temp:
    temp = info[i]
  total+=temp

print(total-sum(info)) #4

---

후기

 

위 문제는 양쪽 끝에서 탐색을 시작한다는 것에만 주의하면 된다.

문제를 분석할 수록 복잡해져서 결국 다른 사람의 풀이를 봤다.

혼자 힘으로 해결할 수 없어서 아쉽지만, 새로운 접근법을 알게 된 문제였다.

 

 

14719번: 빗물