[백준/약점체크] 14719번: 빗물

[문제]

[내 코드]

H, W = map(int, input().split())
blocks = list(map(int, input().split()))

result = 0
for i in range(1, H+1):
    level = []
    for j in range(len(blocks)):
        if i > blocks[j]: level.append(0)
        else: level.append(1)

    for l in range(len(level)):
        before = sum(level[:l])
        after = sum(level[l:])
        if (before>0) and (after>0) and (level[l] == 0) :
            result+=1

print(result)

- 굉장히 어거지로 풀었다.. 층마다 0과 1로 블럭을 쌓았고

- 앞뒤에 최소 한 개의 1이 있을 때의 0들을 더했다

- 통과한 게 신기하다.. 시간이 매우 걸렸다 - 944ms ;;;

 

[개선안]

import sys
input = sys.stdin.readline
H, W = map(int,input().split())
block = list(map(int,input().split()))
answer = 0
 
for i in range(1, W-1):
    left = max(block[ :i])
    right = max(block[i+1: ])
    m = min(left, right)
    if m > block[i]:
        answer += m - block[i]
 
print(answer)

훨씬 빠른 정답... 72ms 

처음 접근했던 방법이랑 같은데.. 포기하지 말고 계속 해볼걸 ㅠㅠ

 

- 첫번째와 마지막에는 빗물이 고일 수 없으니 range(1, w-1) 로 for문을 돌린다

- 양쪽에서 가장 높은 블럭을 찾고, 그 중에서 낮은 블럭을 찾는다

- 현재 블럭과 그 블럭의 차이를 모두 더해주면 된다

 

명쾌하다!!!! 속이 시원함!