섞기 수열/koi_orbit (16 %) (coding)

문제

http://183.106.113.109/pool/koi_orbit/koi_orbit.php?pname=koi_orbit

풀이

처음엔 단순 코딩 문제라 생각하고 막 코딩했는데...입력값 n이 100을 넘어가니 time limit이 뜬다.

Colored By Color Scripter™

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

#include <stdio.h> #include <string.h> #pragma warning(disable:4996) int n, arr[20005], orbit[20005], sort[20005], temp[20005]; int cmp(); int main() {     scanf("%d", &n);     for (int i = 1; i <= n; i++)         scanf("%d", &arr[i]);       for (int i = 1; i <= 20005; i++)     {         if (i > n)             break;         orbit[i] = i;     }         for (int i = 1; i <= n; i++)         sort[arr[i]] = i;       for (int i = 1; i <= 20005; i++)     {         if (i > n)             break;         arr[i] = i;     }       int cnt = 0, flag= 0;     while (1)     {           // change         for (int i = 1; i <= n; i++)             temp[sort[i]] = orbit[i];         memcpy(orbit, temp, sizeof(int) * 20005);           cnt++;           // check         if (cmp())             break;     }     printf("%d\n", cnt); }   int cmp() {     for (int i = 1; i <= n; i++)     {         if (orbit[i] != arr[i])             return 0;     }     return 1; }

문제의 출력 부분에 ' 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.'라고 되어있는데. 이렇게 큰 수가 나올 수 있는 경우에는 그냥 풀어선 모든 테스트 케이스를 통과하기 힘들다.

아래와 같이 표를 그려보니 규칙이 있다는 것을 알 수 있었다.

1	2	3	4	5	6
3	2	5	6	1	4
5	2	1	4	3	6
1	2	3	6	5	4
3	2	5	4	1	6
5	2	1	6	3	4
1	2	3	4	5	6

1 → 3 → 5 (3번)

2 → 2 → 2

4 → 6 (2번)

2의 경우 변경 되는 부분이 없기 때문에 무시하고, 3과 2의 최소 공배수를 구하면 답이 나온다는 것을 알 수 있다.

Code