[백준] 14719_빗물

📕 문제

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

14719번: 빗물

 

💡 풀이법

1. 규칙을 찾기 위해 들여다 보면 해당 인덱스에 빗물이 차는 양은 현애 인덱스의 왼쪽에서 가장 긴 블럭, 오른쪽에서 가장 긴 블럭 중 작은 블럭의 길이만큼 차게 된다.

(단, 양쪽의 긴 블럭중 작은 블럭의 길이가 현재 인덱스보다 작다면 물이 안찬다.

2. for문을 돌며 각 인덱스마다 1번처럼 빗물을 구해서 total에 더해주었다.

3. 난 인덱스를 0부터 W-1 까지 다 보지 않고 양쪽에 물이 아예 못차는 경우를 제외하기위해 start,end를 구해주고 시작했다. 

예를 들어 [0,1,2,1,3,2,4,2,0] 이렇게 블럭이 있을때 빨간색으로 칠해진 숫자 사이만 빗물이 채워지고 가쪽은 빗물이 찰 수 가 없다.

 

H, W = map(int, input().split())
blocks = list(map(int, input().split()))
start = 0
end = len(blocks)-1

while True:
    if blocks[start] > blocks[start+1]:
        break
    start += 1

while end:
    if blocks[end] > blocks[end-1]:
        break
    end -= 1

total = 0
for i in range(start+1, end):
    max_block = min(max(blocks[:i]), max(blocks[i+1:]))
    if blocks[i] < max_block:
        total += max_block - blocks[i]
print(total)