[백준] 14719 빗물 파이썬

문제

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

14719번: 빗물

 

---

풀이

가장 아래쪽부터 반복문을 돌며 왼쪽이 뚫려 있을 때는 -1

막혀있으면 0으로 바꿔주고 그 다음 블록부터 카운트를 시작해서 비어있는 칸이 있을 때마다 1씩 더해줬다.

O(n^2)이라 이게 될까? 싶었는데 통과했다.

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

answer = [0]*h

for i in range(h):
    t = -1
    for j in range(w):
        if heights[j] > i:
            if t == -1:
                t = 0
            else:
                answer[i] += t
                t = 0
        else:
            if t != -1:
                t += 1

print(sum(answer))

 

---

다른 사람의 풀이

그래도 더 좋은 풀이가 있을 것 같아 찾아봤다.

import sys
input = sys.stdin.readline
H, W = map(int,input().split())
block = list(map(int,input().split()))
answer = 0
 
for i in range(1, W-1):
    left = max(block[ :i])
    right = max(block[i+1: ])
    m = min(left, right)
    # 좌우의 블럭 높이의 최댓값 중 작은 값이 현재 블록보다 크다면
    # 반대쪽 값도 그 블럭보다 크다. 따라서 작은 값 - 현재블럭 높이 만큼 ans에 저장.
    if m > block[i]:
        answer += m - block[i]
 
print(answer)

출처: https://hbj0209.tistory.com/140

그 블록을 기준으로 더 낮은 값을 찾는 방법이다.

반복문 하나에 max를 사용했다