백준 8982 수족관1 :: 들짐승

<링크>

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

<풀이>

1. 배열에 수평선의 각 index마다 총 깊이가 몇인지를 기록한다.

2. 구멍이 몇 열에 위치했는지 벡터에 집어넣는다.

깊이는 각 열마다의 총깊이이고, 시작깊이는 물이 시작되는 깊이이다. 맨 처음에는 물이 꽉차있는 상태이기 때문에 시작깊이는 모두 0이다.
구멍이 있는 열은 1, 3이다. 연속된 같은 깊이에서의 구멍은 여러 개가 있던, 어느 곳에 있던 상관없이 하나로 취급해도 된다. 따라서 그냥 3열이라고 했다. 4열에 구멍이 있다해도 똑같다.

3. 구멍이 있으면 그 열의 시작깊이는 총깊이와 같게 된다. 

적어도 해당구멍의 열의 물은 다 빠져나가기 때문이다. 그후 좌측, 우측으로 쭉 훑는데 어떻게 훑냐면

int cur = hall[i];
int h = depth[cur];
startDepth[cur] = h; //현재 구멍자리
//왼쪽 ㄱㄱ
for (int j = cur - 1; j >= 0; --j)
{
    if (h > depth[j])
        h = depth[j];
    if (startDepth[j] < h)
        startDepth[j] = h;
}

h는 3으로 시작했고, 우측으로 훑을 때 녹색칸에서 h가 2로 바뀐다.

4. 위 과정들을 모든 구멍에 대해 반복한 후
5. 각 열마다 깊이-시작깊이 값을 모두 더해주면 남은 물의 양이 된다.