[백준/파이썬]14719번 빗물

 

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

14719번: 빗물

고민만 삼십 분 정도 했던 문제인 거 같다..

정답

def check_left_wall(idx, world) :
    for k in range(idx-1, -1, -1) :
        if world[k] > world[idx] :
            return True
    return False

def check_right_wall(idx, world) :
    for k in range(idx+1, len(world), 1) :
        if world[idx] < world[k] :
            return True
    return False


h, w = map(int, input().split())
world = list(map(int, input().split()))
rain_water = 0

for i in range(1, w-1, 1) :
    while check_left_wall(i, world) and check_right_wall(i, world) :
        world[i] += 1
        rain_water += 1

print(rain_water)

오랜만에 깔끔하게 풀었던 문제다 ㅎㅎ

나는 이 문제를 풀때 빗물이 들어갈 칸을 +1씩 해주며 빗물이 들어갈 칸의 개수를 구했다.

 

알고리즘을 설명하자면.

 

예시입력 

4 8
3 1 2 3 4 1 1 2

 

1. world리스트를 [3, 1, 2, 3, 4, 1, 1, 2] 이렇게 저장하고 인덱스 1부터 7까지 반복을 돌린다.

2. 인덱스 1번일때, 좌 우측에 벽이 있는지 확인한다.

3. 양쪽에 벽이 있으면 빗물이 찰 수 있는 칸이므로 +1해 주고 rain_water변수에도 1을 더해준다.

4. 이 과정을 n-1번 인덱스 까지 반복한다.

 

for문안에 world리스트를 출력하면 다음과 같이 빗물이 채워지는 모습을 볼 수 있다.

마지막 리스트 값을 보면

 

빗물이 다 찬 이미지와 같은 값이 나오게 된다.

 

나는 이렇게 문제를 풀었다.

 

 

---

역시 알고리즘은 구현 문제가 제일 재밌는것 같다.