[백준 10167번] 금광

---

10167번: 금광

---

 

목차

• 사전 지식
• 문제 접근
• 문제 풀이

 

 

사전 지식

• 2차원 좌표 압축에 대한 개념을 알고 있어야 한다.
• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크)

 

 

 

문제 접근

• 이 문제에 대한 순차적인 접근은 여기를 참고하기 바란다.

 

 

 

문제 풀이

이 문제의 핵심은 답이 되는 경우를 얼마나 효율적으로 탐색하는가이다.

(좌표 압축을 했다는 가정 하에) 가장 기초적인 방법은 후보가 되는 직사각형을 모두 살펴보는 것이고

이는 왼쪽 세로, 오른쪽 세로, 위 가로, 아래 가로를 선택하면 되므로 약 $N^4$가지의 경우가 나온다.

 

정답 풀이는 위 가로, 아래 가로 쌍만 살펴보며 답을 구하는 것이다.

이렇게 하면 $N^2$가지의 경우만 살펴보면 되기 때문에 답을 구할 수 있다.

우리가 해야 할 일은 위 가로와 아래 가로를 선택했을 때의 최적의 왼쪽 세로, 오른쪽 세로를 어떻게 구하냐는 것이다.

 

위 가로와 아래 가로를 확정 지었을 때 최적의 왼쪽 세로, 오른쪽 세로를 구한다는 말은

일차원에서 가장 큰 연속합을 구하는 문제로 바꿀 수 있다. (이 부분이 이해가 안 된다면 여기를 참고 바람)

(이를 구하는 법은 DP와 세그먼트 트리 풀이가 있으며, 이 문제 특성상 세그먼트 트리가 더 효율적이다)

 

정리하면, 위 가로와 아래 가로의 모든 쌍을 살펴보며 세그 먼트 트리를 이용하여 최적의 사각형(값)을 빠르게 찾아내는 것이다.