14719. 빗물

업데이트 시간 : 2023-03-21 01:59:56 +0000

[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 31256 KB, 시간: 40 ms

분류

구현, 시뮬레이션

문제 설명

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

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

입력

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

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

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

출력

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

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

💡 Solutions

📄 빗물.py

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

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

idx = 0
max_H = 0
# 높이가 최대인 값 기둥의 위치를 찾아둡니다.
for i, col in enumerate(column):
    # 이 때, 기둥의 높이가 같을 수 있고, 
    # 기둥의 높이가 같을 경우 물이 차지 않기 때문에 
    # 그 부분을 파악하기 위해 같은경우 idx을 업데이트를 하려고
    # 이하 부등호를 사용했습니다.
    if max_H <= col:
        idx = i
        max_H = col

Hole = 0 # 물이 차는 곳
target = column[0] # 첫 시작
for i in range(idx):

    # 물이 찰 수 있는 기둥의 최대 높이가 현재 기둥보다 작을 경우
    if target < column[i]:
        target = column[i] # 기둥 업데이트
    # Target 기둥이 더 클경우
    elif target > column[i]:
        Hole += (target - column[i]) # 물을 담음

# 역순으로 진행
target = column[-1]
for i in range(W-1,idx,-1):
    if target < column[i]:
        target = column[i]
    elif target > column[i]:
        Hole += (target - column[i])

    # if column[idx] == target: 
    # # target으로 하는 높이가 idx에 해당하는 기둥에 도달했을 경우 break
    # # 인덱스로 작업하지 않은 이유는
    #     break


print(Hole)