[BaekJoon] 백준 14719 빗물

[BaekJoon] 백준 14719 빗물

 

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

 

내코드

 

처음에는 왼쪽부터 시작해서 start, end 변수를 갱신해가며 구해줬다.

하지만 28 100 10 20 과 같이 마지막에 작은 값으로 끝나는 경우 저리가 어려워 실패했다.

 

그래서 서칭을 통해 찾은 방식은 다음과 같다.

1. for문으로 가로 전체를 돌아준다.

2. 현재 위치(i)의 왼쪽과 오른쪽 각각에서 최대값을 찾는다.

3. 2에서 찾은 두 값 중 더 작은 값을 찾는다.

4. 3에서 찾은 값과 현재 위치(i)의 높이의 차를 계산한다.

5. 4에서 계산한 값이 현재 위치에서 물이 차오르는 정도이다. 따라서 결과 값에 더해준다.

 

구현 문제가 나오면 대응을 잘 못하는 것 같다.

아무래도 문제를 많이 풀어보지 않은 것도 한몫 하는 것 같아서

많이 풀어봐야겠다.

 

# BaekJoon14719.py

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


def solve():
    global W, arr
    result = 0
    for i in range(W):
        max_left = max(arr[:i+1])
        max_right = max(arr[i:])
        lowest = min(max_left, max_right)
        result += abs(arr[i] - lowest)
    return result


print(solve())

 

참고

https://jjangsungwon.tistory.com/121