[백준 14719번] 빗물 - 파이썬

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

 

 

💡문제 분석 요약

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

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

💡알고리즘 설계

 

1. 첫번째 블록과 마지막 블록을 제외하고 모든 블록을 하나씩 검사한다.

2. 해당 블록을 기준으로 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록의 높이를 구한다.

3. 그 두 블록 중 낮은 블록의 높이가 현재 블록의 높이보다 높다면,

 그 블록에서 현재 블록의 높이를 뺀 값을 빗물의 총량에 더한다

💡코드

H, W= map(int,input().split())

block = list(map(int,input().split()))
count=0

for i in range(1, W-1):
    left_max=max(block[:i])
    right_max=max(block[i+1:])
    wall=min(left_max, right_max)
    if wall>block[i]:
        count+=wall-block[i]
        
print(count)

💡시간복잡도

W는 최대 500이다. 모든 블록을 하나씩 훑고, 한 블록마다 좌우의 전체 블록에서 최대값을 구한다

따라서 498*500(좌우에서 최대값 찾음)이므로

시간 복잡도는 O(N^2)이다. 

💡 느낀점 or 기억할 정보

좌우에서 전체 블록을 검사해 최대값을 찾으면 시간이 오래걸릴거라고 생각했는데, 블록이 500개밖에 없으므로 매번 모두 검사하고 최대값을 찾아도 시간이 충분했다.