[BOJ 3163] 완전탐색 2 - 떨어지는 개미

처음에는 완전탐색으로 풀려고 해봤다.
N개에 개미에 대해 최대 L번 돌려야하니 시간초과가 날 수 밖에없다.

구현보다는 아이디어가 어려운 문제였다.

아이디어

1. 충돌을 해도 결국 떨어지는 시간은 또같다.
   그냥 몸이 바뀐것과 마친가지로 쭉 가게된다.

2. 충돌시 -방향과 +방향의 각각의 총합은 일정하다.

3. 떨어지는건 어차피 가장자리 부터 떨어져야 한다.
   
   이그림으로 예시를 들면
   +가 3개 -가 3개로 결국 0에 가까운 3개의 개미가 -을 L에 가까운 3개의 개미가 +를 가지게된다.
   즉) +4 +5 -1은 0으로 떨어지고 -1 -3 -2 는 30으로 떨어진다

실제 풀이

개미들을 목적 거리만큼 입력을 받고

a < 0 ? ant.push_back({ p, a }) : ant.push_back({ L - p, a });

입력받은 개미들을 거리에 대해 정렬한다.

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

먼저 떨어지는 개미부터 음수인 ID를 가진 개미면 0에 가까운 개미를 떨어트린다.
반대의 경우 L에 가까운 개미를 떨어트린다.

if (i != N-1 && ant[i].first==ant[i+1].first) // 같이떨어지는경우
{
	if (frontValue < backValue) { // id작은게 먼저 떨어짐
		answer.push_back(frontValue);
		answer.push_back(backValue);
	}
	else {
		answer.push_back(backValue);
		answer.push_back(frontValue);
	}
	i++;
	idList.pop_front();
	idList.pop_back();
}
else if (ant[i].second < 0) {
	answer.push_back(frontValue);
	idList.pop_front();
}
else {
	answer.push_back(backValue);
	idList.pop_back();
}