14719(빗물) - 해결

빗물

 

문제

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

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

 

입력

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

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

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

 

출력

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

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

---

높이가 굳이 주어진걸 생각해서 전체 맵을 만들고자 하였다.

물의 양을 구하는 방법은 밑에 한 줄씩 검색을 하는데 벽이 중간이 뜨는 경우는 없기 때문에 

1과 1로 둘러 쌓인 부분을 카운트하기로 하였다.

왼쪽부터 카운트를 하는데 처음 1인 부분을 찾아은 다음, 한칸씩 이동하면서 0이면 카운트하다가 1이 나오면 전체 물양을 증가하면서 카운트를 초기화.

import sys
input = sys.stdin.readline

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

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

# 맵 만들기
maps = [[0] * W for _ in range(H)]

# 블록 쌓기
for j in range(W):
    for i in range(blocks[j]):
        maps[H-1-i][j] = 1

# 물양
total = 0
# 밑에서부터 확인
for i in range(H-1,-1,-1):
    # 각 줄의 물양
    cnt = 0
    # 줄에 1이 있으면 거기부터 시작
    if 1 in maps[i]:
        idx = maps[i].index(1)
    # 없으면 비어있는 거기 때문에 다음
    else:
        continue

    # 1 다음 1을 찾아서
    for j in range(idx+1,W):
        # 1이면 그동안 0갯수 만큼 더하고 0으로 초기화
        if maps[i][j]:
            total += cnt
            cnt = 0
        # 0이면 물을 추가
        else:
            cnt += 1

print(total)