[BOJ/백준][Gold3] 2487 : 섞기 수열 (C++)

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

 

[난이도] Gold3
[유형] 수학

[풀이]
각 카드가 몇번에 섞기 만에 원래 자리로 돌아올 수 있는지를 구하고,
0번인 카드를 제외한 이들의 최소공배수를 구하면 이것이 수열의 궤적이다.
각 카드마다 섞기 횟수를 구하면 시간초과가 나기 때문에
만약 1->3->5->1 이라면 1,3,5 전부 3번만에 원래 자리로 돌아오기 때문에 1을 구하면서
3,5도 같이 3으로 기록해줘야 한다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2487.cpp

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N,v[20001],cycle[20001];
ll gcd(ll a,ll b){
    ll c;
    if(a<b) swap(a,b);
    while(b!=0){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&v[i]);
    for(int i=1;i<=N;i++){
        if(cycle[i]!=0) continue;
        int k=i,cnt=1;
        vector<int> l;
        l.push_back(k);
        if(v[k]==i) cnt=0;
        while(v[k]!=i){
            k=v[k];
            l.push_back(k);
            cnt++;
        }
        for(int w : l) cycle[w]=cnt;
    }
    sort(v+1,v+1+N);
    ll ans=1;
    for(int i=1;i<=N;i++) {
        if(cycle[i]!=0) ans = lcm(ans,cycle[i]); 
    }
    printf("%lld",ans);
}