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

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

14719번: 빗물

문제 요약 : 2차원 공간의 세로길이, 가로 길이가 주어지고, 블록들의 높이가 주어진다. 고인 빗물의 총량을 구하여라.

예제 입력 1

4 4
3 0 1 4

예제 출력 1

5

 

시도 )

벽을 계산해야겠다고 생각했다.

처음에는 벽이 없으므로 False로 시작한다. 0이면 계속 벽이 없는 상태이고, 0이 아니면 벽으로 지정한다.

벽이 지정된 이후로는 벽보다 작은 값들은 tmp에 저장된다.

벽이 세워지고 만약 벽보다 큰 값이 생기면, 그 사이의 고인 물을 계산하게 하였다.(tmp를 pop하여서 계산)

 

이렇게 풀면 예제는 다 풀리지만, 

3 6
5 4 1 3 2

출력값 : 3

위의 문제가 풀리지 않는다.

위의 문제를 2 3 1 4 5 로 뒤집고 다시 풀면 값이 나오지만, 언제는 뒤집고 언제는 안뒤집고 이런것도 모르겠고, 앞 뒤로 도는 것도 시간낭비라고 생각이 들었다.

 

# 빗물
H, W = map(int,input().split(' '))
block = list(map(int,input().split(' ')))

wall = False
tmp = []
answer = 0
for i in range(len(block)):
    if wall == False :
        if block[i] == 0 :
            continue
        else:
            wall = block[i]
            tmp = list()
    else :
        if wall > block[i] :
            tmp.append(block[i])
        else :
            wall = min(wall, block[i])
            while tmp :
                answer += wall - tmp.pop()
            wall = block[i]
wall = block[-1]
while tmp :
    answer += wall - tmp.pop()

print(answer)

 

 

📌 풀이 )

하루를 쉬고, 오늘 kb 라이프 생명 코테를 본 후에 다시 풀었다.

구현 문제를 푼 덕분(?)인지 뭔가 새로운 관점에서 문제를 볼 수 있었다.

 

위의 풀리지 않은 예시에서 힌트를 얻었다.

벽을 현재 벽값보다 클 때마다 갱신하는 것이 아닌, 한 단위로 벽을 계산하기로 하였다.

 

1. 먼저 블록의 개수만큼 for문을 돈다.
2. 현재 블록 기준으로 왼쪽에서 가장 큰 값과 오른쪽에서 가장 큰 값을 계산한다.
3. 각각의 큰 값들이 현재 값보다 크다면,
   1. 현재 블록은 물이 고일 수 있다.
   2. 작은 값을 기준으로 물이 고이기 때문에 wall에 left와 right 중 min 값을 넣어준다.
   3. wall에 현재 블록의 값을 빼주면 현재 블록에 고인 물을 값을 구할 수 있다.
4. 만일, 오른쪽 왼쪽 큰 값중 작은 값이 현재 값보다 작을 경우, 물이 고일 수 없다.(내가 wall 역할을 함)

 

# 빗물
H, W = map(int,input().split(' '))
block = list(map(int,input().split(' ')))
answer = 0

for i in range(1,len(block)-1):
    left = max(block[:i])
    right = max(block[i+1:])

    wall = min(left,right)

    if wall > block[i]:
        answer += wall - block[i]

print(answer)