[백준 14719] 빗물 (python)

 

풀이

block을 차례로 순회하면서 첫 블록보다 크거나 같으면 첫 블록까지 쌓인 빗물을 센다.

그리고 해당 블록을 첫 블록으로 해준뒤 다시 block을 순회한다. 

 

그런데 이 방법으로 풀면 아래의 반례를 통과하지 못한다. 

 

3 6

5 4 1 3 1 2

answer :  3

 

그래서 나는 크거나, 마지막 블록인 경우에 블록을 뒤에부터 순회하며 쌓인 빗물을 셌다.

순회하다가 기준 블록보다 큰 블록을 발견하면, 그 블록을 기준으로 삼아 마저 순회한다. 

 

코드

H, W = map(int,input().split(" "))

block = list(map(int,input().split(" ")))

tmp_h = block[0]
tmp_st =0
ans = 0

for i in range(1, len(block)):
  if tmp_h <= block[i] or i == W -1:
    tmp_m = min(tmp_h , block[i])
    for j in range(i-1, tmp_st , -1):
      if tmp_m < block[j]:
        tmp_m = block[j]
        continue
      ans += tmp_m - block[j]
    tmp_st = i
    tmp_h = block[i]
  elif tmp_h > block[i]:
    continue
print(ans)