[알고리즘] 빗물 - 구현

문제

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

문제 풀이법

1. 처음과 끝에 벽이 있어야만 물을 채울 수 있다.

2. 관점의 문제이다. [ 현재 기점으로 좌우를 비교하냐? 현재 기점으로 뒤만 비교하냐 ]

- 나의 경우, 실패 사례는 현재 기점으로 뒤만 비교했다

 

문제 코드

[ 실패 사례 ]

h,w = map(int,input().split())
blocks = list(map(int,input().split()))

cur_height = blocks[0]
amount = 0
among_block = []

for i in range(w):
    flag = False
    
    if blocks[i] <= cur_height and i != 0:
        among_block.append(blocks[i])
    elif blocks[i] > cur_height:
        flag = True
        cur_height = blocks[i]

    if i == w-1:
        flag = True
    
    if flag:
        for j in among_block:
            amount += abs(j - max(among_block))
        
        among_block = []

print(amount)

 

테스트 코드는 전부 통과를 하는데, 왜 틀린지 아직 의문이다,,,,,

 

[ 성공 사례 ]

 

h,w = map(int,input().split())
blocks = list(map(int,input().split()))
ans = 0

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

    wall = min(left, right)

    if blocks[i] < wall:
        ans += wall - blocks[i]
print(ans)