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

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

14719번: 빗물

---

1. 접근 방식

• 행 한 줄씩 접근하여 빈 블록의 개수를 세자.

 

문제에 제시된 그림으로 예시를 들 때, 1번 열에 있는 블록의 높이가 3이고, 다음으로 높이가 3 이상인 열은 4번 열이므로 1번과 4번 열 사이인 2번 열의 블록 높이는 1이니까 빈 칸은 3 -1 = 2개이고, 3번 열의 블록 높이는 2이니까 빈 칸은 3 - 1 = 1개이니까 3개의 빈 공간에 빗물이 쌓이겠네... 이렇게 생각하는 건 복잡하다.

 

따라서 높이가 1일 때, 2일 때, 3일 때...를 각각 따로 생각하자. 예를 들어 높이가 1인 모든 칸에는 블록이 존재하므로, 빗물이 고이지 않는다. 높이가 2일 때는 1번 열과 3번 열 사이에 빈 공간이 있으므로 (기존 빗물 + 1)이 되고 이어서, 5번 열과 8번 열 사이에는 2개의 빈 공간이 있으므로 (기존 빗물 + 2)가 된다.

 

 

• 블록의 높이가 N 이상인 열을 저장하는 prev 변수가 필요하다.

왼쪽 열과 오른쪽 열이 있어야 그 사이에 고인 빗물 용량을 알 수 있다. 따라서 prev 변수를 -1로 초기화하고, 높이가 N 이상인 열을 만났을 때 prev 값이 -1인지 아닌지에 따라 다르게 처리해야 한다.

높이가 N 이상인 열을 만났을 때 만약 prev 값이 -1이라면 왼쪽 열이 아직 없다는 의미이므로, prev = 해당 열로 설정한다. prev 값이 -1보다 크다면, 이미 왼쪽 열이 설정되어 있다는 의미이므로 해당 열과 prev 열의 차이만큼 빗물이 고여 있을 것이다.

 

 

 

2. 정답 코드

def solve(n):
    prev = -1
    result = 0
    for i in range(W):
        if blocks[i] < n:
            continue

        if prev > -1:
            result += i - prev - 1
        prev = i

    return result


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

answer = 0
for h in range(1, H + 1):
    answer += solve(h)

print(answer)