[BOJ/Gold 4] 백준 2487 섞기 수열(C++)

문제 링크

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

2487번: 섞기 수열

 

문제

A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서 나열하는 것이다. 예를 들어, N = 6이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 카드의 처음 상태가 [A1, A2, A3, A4, A5, A6]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.

[A3, A2, A5, A6, A1, A4]

이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [A5, A2, A1, A4, A3, A6]이 되고, 다시 한 번 더 섞기를 실행하면 카드의 순서가 [A1, A2, A3, A6, A5, A4]가 된다. 이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [A1, A2, A3, A4, A5, A6]이 된다. 처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다. 두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.

출력

첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.

예제 입력 1

6
3 2 5 6 1 4

예제 출력 1

6

알고리즘 분류

• 수학
• 순열 사이클 분할

풀이

순열 사이클 분할(Permutation Cycle Decomposition)

1부터 N까지로 이루어진 N개의 숫자를 갖는 수열들 중, A[X]를 A[X]번째 위치로 배치한다. 배치를 반복하면서 원래 순열이 다시 나타났을 때 반복한 횟수를 구한다. 즉 처음 상태가 나타날 때까지 계속 순열을 섞었을 때의 섞기 궤적, 그러니까 순열 수열의 주기를 구하는 문제이다.

본인은 순열 사이클 분할의 자세한 설명은 여기를 참고하였다.

55. Permutation Cycle Decomposition

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 20001

using namespace std;
int N;
int S[MAX];
bool visited[MAX];
int Answer = 1;

// 순열 사이클 분할(Permutation Cycle Decomposition)
int GCD(int N, int M) {
	while (1) {
		int R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

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

void Settings() {
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			int K = 0;
			for (int j = i; !visited[j]; j = S[j]) {
				visited[j] = true;
				K++;
			}
			Answer = Answer / GCD(Answer, K) * K;
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}