[백준 14719] 빗물

문제

www.acmicpc.net/problem/14719

14719번: 빗물

 

처음 작성한 코드

import sys

h, w = map(int, sys.stdin.readline().split())

block = list(map(int, sys.stdin.readline().split()))
rain = 0

for i in range(w):
    left_max = max(block[:i+1])
    right_max = max(block[i:])
    point = min(left_max,right_max)
    rain += abs(point - block[i])

print(rain)

1. 자신을 포함한 왼쪽에서 제일 높은 블럭을 구한다.
2. 자신을 포함한 오른쪽에서 제일 높은 블럭을 구한다.
3. 1번과 2번에서 구한 블럭 중 더 낮은 블럭을 구한다. 이를 기준으로 빗물이 고일 것이기 때문
4. 현재 인덱스와 더 낮은 블럭(3번에서 구한 블럭)과의 차이를 더해준다.

 

깨달은 점

• 사실 다른 분 코드 보고 짰다.. 처음에 생각한 방법은 현재 인덱스에서 오른쪽으로 가면서 나보다 높은 블럭을 만나기 전까지 만났던 블럭들의 차이를 더해주는 식으로 짜려고 했는데 생각해보니 그럼 나보다 낮은 애들이 나오면 어쩌지? 라는 생각에 계속 정체됐던 것 같다.. 사람들은 너무 똑똑행!