백준 : 1091

주어진 순열 S를 사이클로 분해하면, 이 순열의 주기는 각 사이클의 길이의 최소공배수와 같습니다.
따라서 N≤48에서 나올 수 있는 가장 큰 주기는 사이클의 길이가 3,5,7,8,11,13일 때 120,120 입니다.

 

 

시뮬레이션 문제인데 구현은 그렇게 어렵지않다 P 와 S를 이용해서 카드를 셀럭트하고 조건에 맞는 카드가 나오면 for문을 빠져나오면된다. arrayList를 쓰는것보다 boolean 값을 48(카드의 최대수)를 지정하면 빠르게 확인이 가능하다.

 

중요한점은 카드를 썩는것이 어느정도를 썩으면 다시 원래의 형태를 오게하는지 그것이 문제다.

처음시작 0 1 2 3 4 5 의 카드가 오면 종료시키는 방법도있고 100만번 아래에서는 어쨋든 하나의 루프를 돈다.

 

따라서 for문을 100만번 설정해주고 시뮬레이션을 돌리면 풀수있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 카드섞기 {
	static int N;
	static int P[];
	static int S[];
	static int card[];
	static int copy[];
	static boolean finish[][] = new boolean[3][48];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		card = new int[N];
		copy = new int[N];
		P = new int[N];
		S = new int[N];
		// P 입력 최종적으로 가야할 카드
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			P[i] = Integer.parseInt(st.nextToken());
		}
		// S 입력 섞는 방법
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			S[i] = Integer.parseInt(st.nextToken());
		}
		// 플레이거가 가져야하는 카드
		for (int i = 0; i < N; i++) {
			finish[P[i]][i] = true;
			card[i] = i;
		}

		int ans = -1;

		for (int cnt = 0; cnt <= 120121; cnt++) {

			// pirnt 확인
//			System.out.println(Arrays.toString(card));

			// card가 원하는 사람에게 적절히 나누어 젔는가.
			boolean isPossible = true;
			for (int i = 0; i < N; i++) {
				if (!finish[i % 3][card[i]]) {
					isPossible = false;
					break;
				}
			}

			if (isPossible) {
				ans = cnt;
				break;
			}
			// S로 썩자
			for (int i = 0; i < N; i++) {
				copy[S[i]] = card[i];
			}
			for (int i = 0; i < N; i++)
				card[i] = copy[i];

		}
		System.out.println(ans);
	}
}