[알고리즘][백준] 14719. 빗물

문제

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

 

문제 아이디어 1

처음엔 스택 기반의 문제인 줄 알았습니다. 가장 왼쪽부터 탐색하면서, 왼쪽보다 높은 기둥을 만나면 지금까지 스택에 넣었던 걸 하나씩 꺼내면서 높이를 계산해주고, 가장 왼쪽 기준을 다시 업데이트해주면 될 것이라고 생각했습니다.

예)
3 1 2 3 4 1 1 2 가 있다면,
3을 저장해놓고 다음 3을 만날 때까지 스택에 저장해두고,
3, [1, 2], 3 에서 1 과 2의 높이에 따라 물의 양을 계산해주면 될 것으로 생각했습니다.

 

또한 만약 가장 왼쪽 기준 (위에서는 연산을 다 끝낸 후 4부터 시작) 보다 높거나 같은 기둥이 안 나오면 나머지는 다 빼서 나머지 계산을 하면 될 것이라 생각했습니다.

예)
4 [1 1 2] 까지 저장했는데 더 이상 안 나오면 맨 오른쪽을 끝점으로 해서 4, [1, 1], 2 로 계산하면 되겠다!

 

... 그런데 위처럼 하면 아래의 케이스는 커버를 하지 못했습니다.

반례)
4 8
3 1 2 3 4 1 1 2 1 1 2

 

문제 아이디어 2

결국 우리에게 필요한 건 구글링..! 집단 지성의 힘을 빌려보았습니다.

생각해보면 전체 길이가 500밖에 안되니까 막말로 n ^ 3까지 돌아도 문제가 없더군요? 그래서 아이디어는 아래와 같습니다.

 

예)

문제의 요점은 각 index의 위치에서 가질 수 있는 물의 양을 그냥 하나씩 따로 계산해주는 겁니다.

3 1 2 3 4 1 1 2에서 index=1부터 탐색하면서,

 

1. [3] (1) [2, 3, 4, 1, 1, 2] 중에서  index=1을 기준으로 왼쪽 리스트 중에서 1보다 크고 가장 큰 숫자는 3, 오른쪽 리스트 중에서 1보다 크고 가장 큰 숫자는 4네요? 그러면 index=1은 3 1 2 3 4 로 감싸질테고, 이 경우에 최대 높이가 3까지는 물이 차오를 수 있습니다. 따라서 3 - 1 = 2 만큼을 물의 양에 더해줍니다.

2. [3, 1] (2) [3, 4, 1, 1, 2] 중에서 index=2를 기준으로 왼쪽 리스트 중에서 2보다 큰 가장 큰 숫자는 3, 오른쪽은 4네요? 그렇다면 3, 1, 2, 3, 4 로 감싸진 것 중에서 최대 3만큼 물이 차오를 수 있으므로 3 - 2 = 1을 물의 양에 더해줍니다.

3. ....

 

위의 과정을 계속해서 각 index 별 차오를 수 있는 물의 높이를 더해주면 됩니다! 아이디어만 생각해낼 줄 알면 굉장히 쉬운 문제였습니다..

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

cnt = 0
for idx in range(1, len(pillows) - 1):
    left = max(pillows[ : idx])
    right = max(pillows[idx + 1 :])
    height = min(left, right)
    if height > pillows[idx]:
        cnt += height - pillows[idx]

print(cnt)