[BOJ] 백준 2487 섞기 수열

출처: https://www.acmicpc.net/problem/2487

 Input 

6

3 2 5 6 1 4

　 

 Output 

6　

이 문제를 주어진 카드 순서를 섞기 수열에 맞게 위치를 변경해가며

처음 상태로 돌아왔는지 확인하는 것은 TLE 발생

#include <stdio.h>
 
const int MAX_N = 20000;
int N, arr[MAX_N + 5], pivot[MAX_N], temp[MAX_N + 5];
 
void shuffleCard() {
    for (int i = 1; i <= N; ++i) {
        temp[i] = arr[pivot[i]];
    }
 
    for (int i = 1; i <= N; ++i) {
        arr[i] = temp[i];
    }
}
 
bool checkCard() {
    for (int i = 1; i <= N; ++i) {
        if (arr[i] != i) return false;
    }
    return true;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
 
    for (int i = 1; i <= N; ++i) {
        arr[i] = i;
        scanf("%d", &pivot[i]);
    }
 
    int ans = 0;
    while (true) {
        ans++;
        shuffleCard();
        if (checkCard()) break;
    }
 
    printf("%d\n", ans);
}

규칙과 최소공배수(LCM)을 이용해 답을 도출할 수 있습니다.

1번 자리: ▶ 3 (1 → 3 → 5 → 1, 순서로 처음상태로 돌아옵니다.)

2번 자리: ▶ 1 (2 → 2)

3번 자리: ▶ 3 (3 → 5 → 1 → 3)

4번 자리: ▶ 2 (4 → 6 → 4)

5번 자리: ▶ 3 (5 → 1 → 3 → 5)

6번 자리: ▶ 2 (6 → 4 → 6)

 

최소공배수 LCM (3, 1, 3, 2, 3, 2)를 구합니다.

이때, {1, 3, 5}, {2}, {4, 6}은 각각 동일한 cycle 수를 가지는 것을 확인할 수 있습니다.

따라서 {1}, {2}, {4}로 각 영역의 하나의 값들로만 최소공배수를 구하면됩니다. → LCM(3, 1, 2)

ex) x, y, z의 최소공배수를 구할 때는 LCM(LCM(x, y), z)로 구합니다.

---

#include <stdio.h>
 
const int MAX_N = 20000;
int N, arr[MAX_N + 5];
bool same[MAX_N + 5];
 
int GCD(int B, int A){
    int C;
    while (A != 0) {
        C = B % A;
        B = A;
        A = C;
    }
    return B;
}
 
int LCM(int A, int B){
    return A / GCD(A, B) * B;
}
 
int checkCycle(int start) {    
    int cycleCnt = 1;
    int next = arr[start];
 
    while (true) {
        // 처음 상태로 돌아오는 경우
        if (start == next) {
            return cycleCnt;
        }
        // 같은 cycle에 포함되는 위치 표시
        same[next] = true;
        // 다음 위치
        next = arr[next];
        cycleCnt++;
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
 
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &arr[i]);
    }
 
    // 같은 cycle에 해당하는 것을 제외하고 최소공배수 처리
    int ans = 1;
    for (int i = 1; i <= N; ++i) {
        if (same[i]) continue;
        ans = LCM(ans, checkCycle(i));
    }
    printf("%d\n", ans);
}