January 13, 2023

14719번: 빗물

문제 요약

• 세로 길이 H, 가로 길이 W인 2차원 세계에서 고일 수 있는 비의 총량은?
• 1 ≤ H, W ≤ 500

문제풀이

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

result = 0

for i in range(H):
    for j in range(W):
        if (height_list[j] <= i):
            left = False
            right = False
            for k in range (j):
                if (height_list[k] > i):
                    left = True
                    break
            for k in range (j + 1, W):
                if (height_list[k] > i):
   

• 각 칸을 순회하며 비어있는 칸이라면 좌우가 막혀있는지 확인한다.
• 막혀있는 칸이라면 빗물이 고일 수 있는 칸이다.

시간 복잡도

• $O(HW^2)$

개선할 점

• max 함수를 사용하여 좌우가 막혀있는 칸인지 판별하면 더 간결하게 작성 가능