14719번 - 빗물

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

14719번: 빗물

문제를 처음 봤을 때는 막연하게 2차원 배열을 만들어야 하나? 생각했다. 하지만 조금만 더 생각을 해보면 1차원 배열로도 충분히 풀 수 있다는 것을 알 수 있다. 

문제를 접근한 방식은 아래와 같다.

1. 0번째 인덱스의 값을 max_height라는 리스트에 인덱스와 함께 저장한다. (ex. max_height = [0, 3]) 

2. for 반복문으로 1번째 인덱스부터 접근한다. 이때 max_height와 그 다음 높이를 비교하여 최솟값을 min_value에 저장한다. 위의 그림(i=1)에서 볼 수 있듯이 min_value = 1이 될 것이다. 

3. 그리고 max_value의 인덱스부터 i까지 for 반복문을 돌며 min_value보다 낮은 높이에는 빗물을 채운다. answer라는 변수에 min_value - A[i]만큼 더한다. 이 단계에서 i=1의 그림에서 볼 수 있듯이 빗물이 1만큼 고이게 된다. 따라서 A[1] = 1로 업데이트시켜준다. 즉 min_value의 값을 A[i]에 저장한다.

4. 그리고 해당 인덱스(i)가 max_height의 값보다 크거나 같으면 값을 갱신시킨다. 왜냐하면 그 이전 값을 굳이 탐색할 필요가 없기 때문이다.

5. 2-4의 과정을 반복하면 answer에는 고이게 되는 빗물의 총량을 알 수 있다. 

# 빗물
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = list(map(int, input().split()))
max_height = [0, A[0]]
answer = 0
for i in range(1, W-1):
    min_value = min(max_height[1], A[i+1])
    for j in range(max_height[0], i+1):
        if A[j] < min_value:
            answer += min_value - A[j]
            A[j] = min_value
    if max_height[1] <= A[i]:
        max_height = [i, A[i]]
print(answer)

제출한 최종 코드는 위와 같다.