[BOJ/Python] 백준 14719 빗물

문제

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

풀이

풀이1

• 31256 KB, 144 ms

import sys
input = sys.stdin.readline

H, W = map(int, input().rstrip().split()) # 세로 H, 가로 W
blocks = list(map(int, input().rstrip().split()))

water = 0

for i in range(1, W - 1) :
    flag = True

    while flag :
        if blocks[i - 1] > blocks[i] and i + 1 < W :
            for j in range(i + 1, W) :
                if blocks[i] < blocks[j] :
                    water += 1
                    blocks[i] += 1
                    break
                elif j == W - 1 : flag = False
        else : flag = False

print(water)

풀이1 설명

처음 문제를 보고 스택으로 풀면 되겠다는 생각이 들었으나 막상 코드를 짜려고 하니 복잡해져서 스택 풀이는 포기 ..

각 블럭에 빗물이 고일 수 있는지 한 칸 씩 확인했다.

빗물이 고일 수 있는 조건은

1. 왼쪽에 블럭 벽이나 빗물이 고여있어야 하고

2. 오른쪽 어딘가에 현재 위치보다 높은 블럭이 있어야 한다

한 칸 씩 만 확인해서 효율적인 코드는 아니었지만

input 범위를 보니 시간초과 날 것 같지는 않아서 이 코드로 제출하고 통과

풀이2

• 31256 KB, 44 ms

import sys
input = sys.stdin.readline

H, W = map(int, input().rstrip().split()) # 세로 H, 가로 W
blocks = list(map(int, input().rstrip().split()))

rain = 0

for i in range(1, W - 1) :
    left = max(blocks[:i])
    right = max(blocks[i:])

    tmp = min(left, right)

    if tmp > blocks[i] : rain += tmp - blocks[i]

print(rain)

풀이2 설명

블럭에 빗물이 얼마나 고일 수 있는지 한 칸 씩 넣어보는 것이 아니라 한 번에 고일 수 있는 용량을 구하는 방법 !

i 번째 이전 블럭의 최대 높이와 i 번째 이후 블럭의 최대 높이 중 낮은 블럭의 높이 까지 빗물이 고이게 된다.

빗물이 고이는 높이와 i번째 블럭의 높이의 차가 i번째 블럭에 고이는 빗물의 양이 된다. (단, i번째 블럭의 높이가 더 낮아야 함)

배운 점

단순하게 생각하자