[C++] 백준 2487번: 섞기 수열

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

2487번: 섞기 수열

 

 > 접근

1, 3, 5를 보면, 1 - 3 - 5를 계속해서 반복한다. 2는 계속해서 2이며, 4, 6은 4 - 6을 반복한다.

이 사이클을 나열해보면 1, 2, 3이며, 이것은 6이라는 궤적으로 이어지는데 이 때 최소공배수(Least common multiple)가 쓰이는 것을 알 수 있다.

 

그럼 저 사이클의 길이만 세주면 된다. 사이클의 길이는 입력값(3, 2, 5, 6, 1, 4)을 탐색해주면 알 수 있다. 가령 첫번째 인덱스를 탐색을 하면, 3 -> 5 -> 1이 된다.

또한 각 사이클에 포함되는 원소들은 모두 같은 길이를 가질 것이다.

 

 > 풀이

사이클의 길이를 구할 때, 방문체크를 해주면서 'DFS에서의 사이클 체크'와 비슷하게 함수를 작성한다.

 

#include <bits/stdc++.h>
using namespace std;

int N;
int A[20001];
bool isVisited[20001];

int gcd(int x, int y) {
	if (y != 0) {
		return gcd(y, x % y);
	}
	else {
		return x;
	}
}

long long lcm(long long x, long long y) {
	return (x * y) / gcd(x, y);
}

int getCount(int n, int count) {
	// 이미 방문을 했다는 것은 탐색 시작점이라는 것을 말해준다
	if (isVisited[n]) return count;
	else {
		isVisited[n] = true;
		return getCount(A[n], count + 1);
	}
}

void solution() {
	int i;
	int res = 1;
	for (i = 1; i < N + 1; i++) {
		if (isVisited[i]) continue;
		res = lcm(res, getCount(i, 0));
	}

	cout << res;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	
	int i;
	for (i = 1; i < N + 1; i++) {
		cin >> A[i];
	}

	solution();

	return 0;
}