[BOJ] 3163 - 떨어지는 개미

[백준] 3163 - 떨어지는 개미

아이디어

문제의 조건은 다음의 2가지 가정을 만족한다.

1. 개미가 목적지에 도착하는 시간은 목적지까지의 거리/개미의 속력 = 도착까지 걸리는 시간이 작은 순서로 정렬할 수 있다.
2. 왼쪽에 위치한 개미부터 이동 방향이 음인 개미의 수만큼 순서대로 지점 0에 도착하고, 오른쪽에 위치한 개미부터 이동 방향이 양인 개미의 수만큼 순서대로 지점 b에 도착한다.
   1번 가정은 다음과 같이 증명할 수 있다.
   • 가중치를 고려하지 않고 개미의 이동 시간만을 고려한다면, 두 마리의 개미가 서로 만났을 때 각 개미는 서로를 통과해 지나간다고 가정할 수 있다.
   • 따라서 개미가 서로 마주치는 것과 개미가 도착 지점에 도달하는 시간은 서로 독립적인 관계이다.
   • 개미가 도착 지점에 도달하는 시간을 각 개미의 가중치에 독립적으로 적용할 경우, 두 목적지에 도착하는 시간을 정렬해 작은 순서대로 고려하는 것이 가능하다.

2번 조건을 증명하기 위해서는 먼저 다음 가정이 타당함을 증명해야 한다.

1. 지점 0에 도착하는 개미는 남아있는 개미 중 가장 왼쪽에 위치하는 개미이고, 지점 b에 도착하는 개미는 남아있는 개미 중 가장 오른쪽에 위치하는 개미이다.
   위의 가정은 귀납법을 적용해 다음과 같이 증명할 수 있다.
   1. 가장 왼쪽에 위치한 개미를 1번 개미, 그 다음에 위치한 개미를 2번 개미라고 하고 2번 개미가 1번 개미보다 먼저 지점 0에 위치했다고 가정하자.
   2. 1번 개미와 2번 개미가 가질 수 있는 상태는 다음의 4가지이다.
      • 1번 개미와 2번 개미가 둘 다 음의 방향을 가지는 경우
        • 1번 개미가 2번 개미보다 더 왼쪽에 위치하므로, 1번개미가 2번 개미보다 더 먼저 지점 0에 도착한다. 따라서 모순.
      • 1번 개미가 음수, 2번 개미가 양의 방향을 가지는 경우
        • 2번 개미는 다른 개미와 마주쳐 음의 방향을 가지게 되어야 지점 0에 도달할 수 있다. 다른 개미와 마주쳐 음의 방향을 가지게 되더라도, A와 동일한 상황이므로 모순.
      • 1번 개미가 양수, 2번 개미가 음의 방향을 가지는 경우
        • 1번 개미와 2번 개미가 마주치면 1번 개미가 음의 방향을 가지고 지점 0에 도달한다. 이후 2번 개미가 다른 개미와 마주쳐 음의 방향을 가지게 된다면, A와 동일한 상황이다. 모순.
      • 1번 개미가 양, 2번 개미가 양의 방향을 가지는 경우
        • 2번 개미가 다른 개미와 마주쳐 음의 방향을 가지게 된다면, C와 동일한 상황이다. 모순.

지점 b에 도달하는 개미의 경우 또한 같은 방식으로 증명할 수 있다.
또한 개미가 서로 마주쳐도 전체 개미가 가지는 방향의 총 합은 변하지 않는다. 따라서 지점 0에 도달한 개미+현재 지점 0으로 향하고 있는 개미의 수 음의 방향을 가지는 개미의 수와 같고, 이는 변하지 않는다.
각 지점 0, 지점 b에 도달하는 개미에 대해 가정 3을 적용시킬 수 있다. 따라서 가정 2 또한 옳다.

주의점

k번째로 떨어지는 개미와 같은 시간을 갖는 개미가 존재할 수 있다.(최대 2마리까지 동시에 떨어질 수 있다.)
이는 k-1번째로 떨어진 개미와 k번째 개미, k번째 개미와 k+1번째 개미가 서로 같은 시간을 가질 수 있다는 의미이다.
나는 k번째 개미와 k-1번째 개미만 비교해 여러번의 틀렸습니다를 받았다..
결국 전체 개미를 다시 정렬해 k번째 개미를 다시 출력하는 방법을 사용했는데, k-1과 k, k와 k+1만 비교해도 괜찮지 않을까 하는 생각이 든다. 조금 까다로울 수 있겠지만..

구현

입력을 받을 때 위치와 속력, 방향을 이용해 개미가 도착하는 시간을 계산해 최소힙에 저장한다.(각 시간에 도착한 도착 지점을 함께 pair로 저장한다.)
입력이 끝난 이후, 개미의 초기 위치를 기준으로 오름차순으로 정렬한다.
최소힙에 저장된 원소를 순서대로 pop하면서 배열에 저장하고, 저장된 배열을 시간, 번호 순으로 정렬한다.

시간 복잡도

최소힙에 도착 시간을 저장하는 시간, 개미를 정렬하는 시간은 각각 O(NlogN)이 소요되며, 이후 O(N)시간을 들여 탐색하고, 다시 O(NlogN)시간을 들여 정렬하므로 결론적으로 O(NlogN)시간이 소요된다.

소스코드

#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;

int main(void) {
	int t;
	scanf("%d", &t);
	while (t--) {
		priority_queue<PII, vector<PII>, greater<PII>> pq;
		vector<PII> ant;
		int n, b, k;
		scanf("%d %d %d", &n, &b, &k);
		for (int i = 0; i < n; i++) {
			int w, x, d;
			scanf("%d %d", &x, &w);
			if (w > 0) {
				pq.push({ b - x,1 });
				ant.push_back({ x, w });
			}
			else {
				pq.push({ x, -1 });
				ant.push_back({ x, w });
			}
		}
		int s = 0, e = n - 1, id = 1000000001, last = pq.top().first;
		vector<PII> ans;
		while (!pq.empty()) {
			int t = pq.top().first, type = pq.top().second, now;
			pq.pop();
			if (type == 1) {
				ans.push_back({ t,ant[e--].second });
			}
			else {
				ans.push_back({ t,ant[s++].second });
			}
		}
		sort(ans.begin(), ans.end());
		printf("%d\n", ans[k-1].second);
	}
	return 0;
}