[python] 백준 - 14719. 빗물

🤔문제 해결

• G5 | 구현, 시뮬레이션

며칠 전 nhn 코테 문제랑 비슷한 문제.

그 때는 자바로 풀었기도 하고, 더 복잡하게 푼거같다.

딱히 어려운 기술을 요구하는 문제는 아니다.

1. 오른쪽으로 가면서 자신보다 높거나 같은 블럭을 찾는다.
2. 가는 중에 자신보다 낮지만가장 큰 놈을 찜해 놓는다.
3. 위의 과정이 끝나면 양쪽의 블럭중 낮은 블럭 만큼의 빗물을 사이의 블럭에 채운다.

💻소스 코드

def find_block(x: int) -> int:
    # 오른쪽으로 가면서 자신보다 크거나 같은 블럭을 찾는다.
    # 가는 중에 자신보다 작지만 그 중에 가장 큰 놈을 찜해 놓는다.
    max_block = [0, 0]
    for j in range(x + 1, W):
        if block[j] >= block[x]:
            return j

        if max_block[1] <= block[j]:
            max_block[1] = block[j]
            max_block[0] = j

    return max_block[0]


def fill_rainwater(x: int, y: int) -> int:
    # 자신보다 같거나 큰놈이 없으면 찜해놓은 녀석의 높이만큰 물을 채운다.
    # 자신보다 같거나 큰놈이 있으면 자신의 높이만큼 물을 채운다.
    rainwater = min(block[x], block[y])
    cnt = 0
    for j in range(x + 1, y):
        cnt += rainwater - block[j]
        block[j] = rainwater

    return cnt


if __name__ == '__main__':
    H, W = map(int, input().split())  # 세로 가로
    block = list(map(int, input().split()))
    answer = 0

    i = 0
    while i < W - 1:
        b = find_block(i)
        answer += fill_rainwater(i, b)
        i = b
    print(answer)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

14719번: 빗물