난이도

Gold 5

풀이 참고 유무

X

막힌 부분

X

문제

문제 바로가기

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

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

입력

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

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

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

출력

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

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

예제 입력

4 8
3 1 2 3 4 1 1 2

예제 출력

5

문제 검토

완전 탐색으로 문제를 풀면 될 것 같다.
블록 사이에 물이 차는 조건만 잘 구현하면 된다.

풀이(python)

Python

row,col = map(int,input().split())
world=[[0 for _ in range(col)] for _ in range(row)]
tmp1=list(map(int,input().split()))
for x in range(col):
    tmp=tmp1[x]
    for y in range(tmp):
        world[y][x]=1
blockOn=False     
cnt=0       
result=0    
for x in range(row):
    cnt=0
    blockOn=False
    for y in range(col):
        if blockOn and world[x][y]==0:
            cnt+=1
        if world[x][y]==1:
            blockOn=True
            result+=cnt
            cnt=0
print(result)            

block을 만났다면 blockOn으로 해주고 다음 block을 만나기 전까지 빈 블록 수를 세준다.
다음 block을 만났다면 blockOn은 그대로 유지하되 현재까지 카운트한 빈 블록 수를 결과 값에 넣어준다.

걸린 시간

21:12

총평

골드 5 난이도의 문제는 아닌 것 같다.
문제 이해도 쉽고 구현이 어렵지 않고 특정 알고리즘을 사용하지도 않았다.
실버 3~1 사이의 난이도라고 생각하면 될 것 같다.