BOJ 3163 떨어지는 개미

개미 N마리가 막대 위에 올라가 있다. 일부 개미는 왼쪽을 바라보고 있고, 나머지 개미는 오른쪽을 바라보고 있다. 모든 개미는 매우 작아서 크기가 없는 점으로 나타낼 수 있다. 시작 신호가 주어지면, 개미는 바라보고 있는 방향으로 행진을 시작한다. 모든 개미는 동일한 속도 초속 1mm로 이동한다. 두 개미가 한 점에서 충돌하는 경우가 발생할 수 있다. 이 경우에 두 개미는 행진하는 방향을 반대 방향으로 바꾸고, 행진을 계속하게 된다. 개미가 방향을 바꾸는데 걸리는 시간은 없다. 개미가 막대의 끝에 도착하는 경우에는, 막대에서 떨어지게 된다. 막대는 땅 위에 떠있다고 가정한다.

처음에 모든 개미의 위치는 서로 다르다. 즉, 두 개미가 막대 위의 한 점에 같이 있는 경우는 없다. 개미는 부호 있는 정수로 나타낼 수 있다. 이 정수를 개미의 ID라고 한다. 개미의 ID의 부호는 개미가 처음에 바라보고 있는 방향이다. -는 왼쪽을 바라보고 있는 것이고, +는 오른쪽을 바라보고 있는 것이다. 개미의 ID의 절댓값은 1부터 109까지의 정수 중 하나이다. 또, 모든 개미의 ID의 절댓값은 서로 다르다. 아래 그림에는 개미가 총 6마리가 있고, ID는 {+4, +5, -1, -3, -2, +6}이다. 각 개미의 초기 위치는 {5, 8, 19, 22, 24, 25}이며, 막대의 길이 L = 30이다. 화살표는 처음에 개미가 바라보고 있는 방향을 나타낸다. 왼쪽 끝의 좌표는 0이고, 오른쪽 끝의 좌표는 30이다. ID가 +6인 개미는 시간 t = 5일 때, 막대의 오른쪽 끝에 도착하며, t = 6에 막대에서 떨어지게 된다.

개미가 행진을 시작하기 전의 상태 (ID와 막대 상의 위치)가 주어진다. 두 개미가 동시에 막대의 양 끝에서 떨어지는 경우에는, ID가 작은 개미가 조금 더 먼저 떨어진다고 한다. 아래 그림은 이와 같은 경우를 나타낸 그림이다. 두 개미 {-1, +2}는 끝에 동시에 도착하게 된다. -1 < +2 이기 때문에, ID가 -1인 개미가 +2인 개미보다 조금 더 먼저 떨어지게 된다. 따라서, 아래 그림의 네 개미가 떨어지는 순서는 {-1, 2, 4, 3}이 된다.

양의 정수 1 ≤ k ≤ n이 주어졌을 때, k번째로 떨어지는 개미를 구하는 프로그램을 작성하시오.

---

개인적으로 여태 푼 문제 중 가장 어려운 문제였다.

입력받은 현 위치에서 떨어지는 곳까지의 거리^[각주:1]를 구한 후 오름차순으로 구조체를 정렬시켰다.

정렬된 구조체의 a(인덱스)의 부호에 따라서 arr배열(초기 인덱스^[각주:2])의 앞, 뒤로 pop해서 ans배열에 저장시키면 된다.

이 때 k번째의 앞, 뒤를 확인해서 같은 p(거리)값을 가진다면 a(인덱스)값으로 잘 바꿔주면 된다.

(같은 p(거리)값은 단 2개밖에 없기 때문에 앞, 뒤만 확인해주면 된다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

// 3163 떨어지는 개미 #include<stdio.h> #include<stdlib.h> #define FOR(i,j) for(int i=1;i<=j;i++) typedef struct ant { int p; int a; }ANTS; int func_compare(const void * first, const void * second) { ANTS *v1, *v2; v1 = ((ANTS *)first); v2 = ((ANTS *)second); if (v1->p > v2->p) return 1; else if (v1->p < v2->p) return -1; else return 0; } int main() { struct ant ANT[100001]; int T, N, L, k; int arr[100001], ans[100001]; scanf("%d", &T); while (T--) { scanf("%d %d %d", &N, &L, &k); int head = 1, tail = N; FOR(i, N) { scanf("%d %d", &ANT[i].p, &ANT[i].a); arr[i] = ANT[i].a; if (ANT[i].a > 0) ANT[i].p = L - ANT[i].p + 1; else ANT[i].p++; } qsort(ANT, N + 1, sizeof(ANT[0]), (func_compare)); FOR(i, k + 1) { if (ANT[i].a > 0) { ans[i] = arr[tail]; tail--; } else { ans[i] = arr[head]; head++; } } if (ANT[k].p == ANT[k - 1].p) { if (ans[k] < ans[k - 1]) ans[k] ^= ans[k - 1] ^= ans[k] ^= ans[k - 1]; } else if (ANT[k].p == ANT[k + 1].p) { if (ans[k] > ans[k + 1]) ans[k] ^= ans[k + 1] ^= ans[k] ^= ans[k + 1]; } printf("%d\n", ans[k]); } }

1. 충돌은 무시한다. [본문으로]
2. 변하지 않는다. [본문으로]