3163 떨어지는 개미

이번 3163 떨어지는 개미는, 처음에 물리적 충돌을 고려하다보니 시간초과가 났고, 질문검색을 통해 힌트를 얻어 풀게되었다.

충돌을 생각하지 않고, 현재위치에 있는 개미가 계속 진행하는 형태로(통과한다고 생각) 문제를 풀어나가면된다.

고려해야할 사항은

1) 현재위치, 현재 향하고 있는 방향으로의 거리가 얼마나 되는지

2) 가장 바깥쪽에 있는 개미의 ID가 무엇인지

2가지를 고려한채 거리순으로 정렬 후 현재 향하고 있는 방향의 가장 끝쪽의 개미를 떨어뜨리면 되는 방식이다.

첫번째 테스트케이스의 예제를 아래와 같이 그림으로 표현해보았다.

더 자세한 설명을 위해 소스코드를 아래 올려두었다.

<소스코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

int T,N,L,k,cnt,a,b;
vector<pair<int, int> p;
deque<pair<int, int> d;

int main() {
	scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d", &N, &L, &k);

		for (int i = 0; i < N; i++) {
			scanf("%d%d", &a, &b);
			d.push_back(make_pair(a, b));
			if (b < 0) p.push_back(make_pair(a, b));
			else p.push_back(make_pair(L - a, b));
		}

		sort(p.begin(), p.end());

		p.push_back(make_pair(0, 0));

		for (int i = 0; i < p.size(); i++) {
			if (p[i].second == 0) break;
			if (cnt == k) break;
			if (p[i].first == p[i + 1].first) {
				int q = d.front().second;
				int w = d.back().second;
				d.pop_back();
				d.pop_front();
				if (q < w) {
					a = q;
					cnt++;
					if (cnt == k) break;
					a = w;
				}
				else if (q > w) {
					a = w;
					cnt++;
					if (cnt == k) break;
					a = q;
				}
				i += 1;
				cnt++;
			}
			else {
				if (p[i].second < 0) {
					a = d.front().second;
					d.pop_front();
					cnt++;
				}
				else if (p[i].second >0) {
					a = d.back().second;
					d.pop_back();
					cnt++;
				}
			}
		}

		printf("%d\n", a);

		while (!d.empty()) d.pop_back();

		while (!p.empty()) p.clear();

		cnt = 0;
	}

	return 0;

}