[BOJ 3163] 완전탐색 2 - 떨어지는 개미
처음에는 완전탐색으로 풀려고 해봤다.
N개에 개미에 대해 최대 L번 돌려야하니 시간초과가 날 수 밖에없다.
구현보다는 아이디어가 어려운 문제였다.
아이디어
-
충돌을 해도 결국 떨어지는 시간은 또같다.
그냥 몸이 바뀐것과 마친가지로 쭉 가게된다. -
충돌시 -방향과 +방향의 각각의 총합은 일정하다.
-
떨어지는건 어차피 가장자리 부터 떨어져야 한다.
이그림으로 예시를 들면
+가 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();
}
Author And Source
이 문제에 관하여([BOJ 3163] 완전탐색 2 - 떨어지는 개미), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hereokay/BOJ-3163-완전탐색-2-떨어지는-개미저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)