[Baekjoon - 8982] 수족관 1

난이도: Gold III

 

태그

• Implementation
• Sweeping?

 

풀이

1. 선분보다 더 간단한 표현법이 없을까?

수족관은, 위에서 내려다볼 때 바닥이 모두 보이는 형태입니다.

즉, 하나의 \( x \)좌표는 최대 하나의 수평선분이 차지하고 있다는 의미입니다.

// 엄밀히는, 수평선분을 \( [x_1, x_2) \)의 반열린 구간으로 정의할 때입니다. 앞으로도 이 문제에서는 수평선분을 반열린구간으로 정의하겠습니다.

 

그러니, \( H_x \) = 좌표가 \( x \)인 위치의 깊이 로 수족관의 바닥 상태를 더 간단하게 저장할 수 있습니다.

 

2. 각각의 구멍은, 특정 위치에 있는 물을 얼마나 빼낼 수 있을까?

\( [x_1, x_2) \)의 수평 선분에 구멍이 뚫렸다고 해봅시다.

 

자명하게, \( [x_1, x_2) \) 위치에 있는 물은 모두 빠지게 됩니다.

하지만, 다른 위치에 있는 물들도 같이 빠질 수 있게 됩니다.

 

위치 \( x \)에서 물이 빠지는 양을 \( A_x \)라고 합시다. 그럼, 우리는 이 \( A_x \)의 값을 구하면 됩니다.

1. \( x_1 \le x < x_2 \)일 때의 \( A_x \)는 자명히 \( H_x \)가 됩니다.

2. 아래 그림을 생각해보면, \( x < x_1 \)일 때의 \( A_x \)는 \( \min\limits_{x < x_2} H_x \)가 됩니다.

3. \( x_2 \le x \)도 2와 비슷하게 계산할 수 있습니다.

 

2와 3은, \( x_1 \)에서 멀어지는 방향으로 구하면 각 위치별로 \( O(1) \), 총 \( O(N) \)에 구할 수 있습니다.

 

3. 최종 답은?

각각의 구멍은 독립적으로 작용하므로, \( K \)개의 구멍에 대한 \( \max A_x \)를 구할 수 있습니다.

그럼, 그 위치에서 남게 되는 물은 빼내지 못한 물의 양, 즉 \( H_x - \max A_x \)가 되겠죠.

이를 모두 더해주면 됩니다.

 

시간 복잡도는, 구멍의 개수가 최대 2500개이고, 위치의 개수는 최대 40000이므로 정확히 1억이 나옵니다.

 

4. 코드

carbon.now.sh