[백준] No.13334 - 철로 (C++, 우선순위 큐)

문제

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

13334번: 철로

 

 

풀이

 

solved.ac 난이도: Gold 2

 

입력을 정렬한 후 우선순위 큐를 이용하여 처음부터 끝까지 스위핑하여 해결할 수 있는 문제.

 

일단 입력의 집과 사무실의 위치를 pair<int,int> arr[100000] 에 저장한다.

어느 쪽이 집이고 사무실 인지는 철로에 영향이 없기 때문에 pair의 first에 더 작은 위치(선의 시작점)를 저장하자.

 

이제 arr를 정렬하는 순서를 생각해보자.

아래와 같이 pair의 second를 더 큰 것이 앞으로, 만약에 second가 같다면 first가 큰 것이 앞으로 오도록 정렬한다.

(선의 끝점이 작은 순서대로, 끝점이 같다면 더 긴 선분이 앞으로 )

그 후 가장 앞 pair의 second(일직선에서 끝점)에서 끝에 도달하는 d길이 만큼의 철로를 만든다.

즉, 철로의 포함 범위는 (second - d, second)이다.

 

 

 

현재의 일직선(pair)이 이 철로안에 포함되는 것을 확인하고 싶다면 pair의 first(시작점)이  철로의 시작점 second - d보다 큰지 확인하면 된다.

만약 현재의 선이 철로의 범위에 포함이 된다면 카운트를 늘리고 해당 선의 시작점을  우선순위 큐에 저장한다.

이 우선순위 큐는 최소 힙으로 구현시킨다.

priority_queue<int, vector<int>, greater<int>> min_pq

 

그 이유는 철로가 3번 선의 끝점을 기준으로 생성되어있다고 생각해보자.

더 이상 1번 선은 철로에 포함되지 않는다. (선의 시작점 < 철로의 시작점)

따라서 해당 선은 철로가 포함하는 선을 저장한 min_pq에서 빼주고 카운트를 -1 해주자.

또한 그림과 다른 예제들에서는 새로운 철로에 포함되지 않는 기존의 선들이 많을 수 있으므로 min_pq의 top이 철로의 시작점보다 크거나 같을 때까지 빼내 주자.

 

현재까지 min_pq에 포함된 선의 개수가 해당 철로에서의 포함하는 선의 수이다.

따라서 각 경우마다 최댓값과 비교하여 가장 큰 경우를 찾자. 

 

이러한 과정은 각 선마다 한 번씩만 철로를 생성해 보는 것으로 모든 경우를 확인할 수 있다.

이런 문제처럼 정렬된 정보를 한 번만 순회하는 것으로 정답을 구할 수 있는 것을 스위핑 기법이라 한다.

 

 

 

코드