문제 : https://www.acmicpc.net/problem/3163
서론
모든 개미를 일일이 옮겨서 풀었으나 시간초과.
시간복잡도를 최대한으로 줄였으나 또 시간초과.
결국 구글링을 했는데, 위의 방식으로는 풀수가 없는듯하고 선지자들의 코드는 이해가 안가서 끙끙대다 이틀걸린 문제
풀이
https://www.acmicpc.net/board/view/28512
위의 댓글에서 충돌을 무시하라는 내용을 보게되었으나 이해가 가지 않았다.
그래서 시간초과가 난 코드에서 충돌을 계산하는 부분을 주석처리하고 돌려보았다.
개미가 낙하할때마다 ID, 경과시간, 낙하위치를 출력하는데
충돌이 포함된 결과
| ID | 6 | 4 | -2 | 5 | 3 | -1 |
| 경과시간 | 6 | 20 | 23 | 23 | 25 | 26 |
| 낙하위치 | 오른쪽 | 왼쪽 | 오른쪽 | 왼쪽 | 왼쪽 | 오른쪽 |
충돌이 포함되지 않은 결과
| ID | 6 | -1 | 5 | -3 | -2 | 4 |
| 경과시간 | 6 | 20 | 23 | 23 | 25 | 26 |
| 낙하위치 | 오른쪽 | 왼쪽 | 오른쪽 | 왼쪽 | 왼쪽 | 오른쪽 |
신기하게도 충돌을 무시한 결과는 ID는 뒤죽박죽으로 나오지만 경과시간과 낙하위치가 충돌을 포함한 결과와 일치한다.
이유는 아래 링크를 참고한다.
https://baeharam.github.io/ps/2018/12/31/ps-boj3163/
즉 충돌을 무시하더라도 충돌을 포함했을때와 같은 시간에 같은 위치로 개미가 낙하한다.
그러나 충돌할때 ID는 틀어져버리므로 사용할 수 없다.
이제 언제, 어디서 낙하하는지 알았으니 어떤 개미(ID)가 언제, 어디서 낙하하는지만 알면 된다.
예제의 4, 5, -1, -3, -2, 6에서
현재 왼쪽에서 낙하할 수 있는 개미는 4뿐이다. 5는 4가 낙하하기전까지 절대 왼쪽에서 낙하할 수 없다.
반대로 현재 오른쪽에서 낙하할 수 있는 개미는 6뿐이다. 2는 6이 낙하하기전까지 절대 오른쪽에서 낙하할 수 없다.
충돌을 포함하지 않은결과의 표를 다시 보자
가장 먼저 낙하하는 개미는 6초에서 오른쪽으로 낙하한다.
현재 오른쪽에서 낙하할 수 있는 개미는 오직 6뿐이다.
6이 낙하하면 4, 5, -1, -3, -2가 남는다.
이제 20초에 왼쪽에서 개미가 낙하해야하는데, 왼쪽에서 낙하할 수 있는 개미는 오로지 4뿐이다.
4가 낙하하면 5, -1, -3, -2가 남는다.
이제 23초에 오른쪽, 왼쪽에서 개미가 낙하해야하는데, 오른쪽에서 낙하할 수 있는 개미는 오로지 -2뿐이고 왼쪽에서 낙하할 수 있는 개미는 오로지 5뿐이다. 문제에서 ID가 작은것이 먼저 낙하하라고 했으므로
-2가 낙하한다.
-2가 세번째로 낙하했다. 답이다.
즉 충돌을 무시한 결과의 경과시간과 낙하위치
그리고 막대위의 개미순서만 있으면 문제를 해결할 수 있다.
경과시간과 낙하위치는 다음과 같이 구한다.
| ID | 4 | 5 | -1 | -3 | -2 | 6 |
| 초기위치(x) | 5 | 8 | 19 | 22 | 24 | 25 |
| 경과시간 | 30-5+1=26 | 30-8+1=23 | 19+1=20 | 22+1=23 | 24+1=25 | 30-25+1=6 |
| ID 부호 | + | + | - | - | - | + |
| 낙하위치 | 오른쪽 | 오른쪽 | 왼쪽 | 왼쪽 | 왼쪽 | 오른쪽 |
ID가 양수면 경과시간은 l-x+1, 낙하위치는 오른쪽이다.
ID가 음수면 경과시간은 x+1, 낙하위치는 왼쪽이다.
구현
// c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
int main() {
int t, n, l, k;
cin >> t;
while (t--) {
vector<int>r;
vector<pair<int, int>>v;
deque<int>dq;
cin >> n >> l >> k;
// 개미 입력
for (int i = 0; i < n; i++) {
int lo, id;
cin >> lo >> id;
if (id < 0) {
v.push_back(make_pair(lo + 1, -1));
}
else {
v.push_back(make_pair(l - lo + 1, 1));
}
dq.push_back(id);
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
int front = 0;
int second = 0;
// 낙하순서 계산
while(r.size() < k){
front = v.back().first;
second = v.back().second;
v.pop_back();
if (v.back().first != front) {
if (second < 0) {
r.push_back(dq.front());
dq.pop_front();
}
else {
r.push_back(dq.back());
dq.pop_back();
}
}
else {
if (dq.front() < dq.back()) {
r.push_back(dq.front());
r.push_back(dq.back());
}
else {
r.push_back(dq.back());
r.push_back(dq.front());
}
dq.pop_back();
dq.pop_front();
v.pop_back();
}
}
cout << r[k-1] << endl;
}
}
최근댓글