백준 1091 카드 섞기

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

1091번: 카드 섞기

문제

지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번)

일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런식으로 카드를 나누어 준다. 하지만, 지민이는 약간 사기를 치려고 한다.

지민이는 처음에 카드를 섞기 전에 카드의 순서를 알고 있고, 이 정보를 이용해 각 카드가 특정한 플레이어에게 보내지게 할 것이다.

카드를 한 번 섞을 때는 주어진 방법을 이용해서만 섞을 수 있고, 이 방법은 길이가 N인 수열 S로 주어진다. 카드를 한 번 섞고 나면 i번째 위치에 있던 카드는 S[i]번째 위치로 이동하게 된다.

각 카드가 어떤 플레이어에게 가야 하는지에 대한 정보는 길이가 N인 수열 P로 주어진다. 맨 처음 i번째 위치에 있던 카드를 최종적으로 플레이어 P[i] 에게 보내야한다.

지민이가 목적을 달성하기 위해 필요한 카드 섞는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 3보다 크거나 같고, 48보다 작거나 같은 3의 배수이다.

둘째 줄에 길이가 N인 수열 P가 주어진다. 수열 P에 있는 수는 0, 1, 2 중 하나이다.

셋째 줄에 길이가 N인 수열 S가 주어진다. 수열 S에 있는 수는 모두 N-1보다 작거나 같은 자연수 또는 0이고 중복되지 않는다.

출력

첫째 줄에 몇 번 섞어야 하는지 출력한다. 만약, 섞어도 섞어도 카드를 해당하는 플레이어에게 줄 수 없다면, -1을 출력한다.

예제 입력 1 

3

2 0 1

1 2 0

예제 출력 1 

2

예제 입력 2 

6

0 1 2 0 1 2

1 4 0 3 2 5

예제 출력 2 

0

---

[풀이 과정]

- input : 섞어도 섞어도 카드를 해당하는 플레이어에게 줄 수 없다면 -1을 출력해야 하는데 이를 판단하기 위해 초기 상태를 저장한 배열

- arr, arr2 : 카드를 섞기 전 상태와 섞은 후 상태를 저장할 배열, arr2는 다시 arr에 저장한다. 

- result : 현재 카드(arr)가 몇 번 플레이어에게 갈 건지 저장한 배열(0, 1, 2로만 이루어진 배열)

 

1. p의 상태와 동일해질 때까지 반복문을 실행한다.

- check함수를 사용해서 p의 상태와 동일해졌는지 확인한다. true이면 반복문 종료한다.

- time이 0보다 크고 check_input함수가 true이면 이미 여러 번 섞어서 초기 상태와 동일해졌는데도 p의 상태와 다르다는 것이므로 -1을 출력하기 위해 flag에 false를 주고 반복문을 종료한다.

- 현재 상태가 p와 다르므로 카드를 섞기 위해 mix_card함수를 호출한다.

- 한 사이클 돌았으므로 time을 1 증가시킨다.

 

2. check()

- 0~n-1카드를 확인한다.

- 사람은 0~2번(p_num)까지 있으므로 i가 3의 배수가 되면 p_num을 0으로 바꾼다.

- p배열과 비교하기 위해 result배열을 사용하는데 arr[i]번 인덱스에 p_num을 저장한다.

- 반복문이 끝나면 result와 p배열을 비교해서 하나라도 다르면 false를 반환하고 모두 같으면 true를 반환한다.

 

3. check_input()

- 여러번 섞어서 초기상태와 동일해졌으면 더이상 해볼 필요가 없기 때문에 반복문을 종료 후 -1을 출력해야한다. 이를 위해서 arr와 input이 동일한지 확인한다. time이 0보다 클 때 수행하는 이유는 time이 0일 때는 당연히 arr와 input이 동일하기 때문이다.

 

4. mix_card()

- s배열에 따라 카드가 섞이므로 arr2[s[i]]에 arr[i]를 저장한다.

- 이후 arr2에 있는 모든 값을 arr로 이동시킨다.

- 다음 사용을 위해 arr2를 0으로 초기화한다.

 

5. flag가 false이면 -1을 출력하고 아니면 time을 출력한다.

---

[소스 코드]

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 50;

int n, input[MAX], arr[MAX], arr2[MAX], result[MAX], p[MAX], s[MAX];

bool check() {
	int p_num = 0;
	for (int i = 0; i < n; i++) {
		if (i % 3 == 0) p_num = 0;
		result[arr[i]] = p_num++;
	}

	for (int i = 0; i < n; i++) {
		if (result[i] != p[i]) return false;
	}
	return true;
}

void mix_card() {
	for (int i = 0; i < n; i++) {
		arr2[s[i]] = arr[i];
	}
	
	for (int i = 0; i < n; i++) arr[i] = arr2[i];
	memset(arr2, 0, sizeof(arr2));
}

bool check_input() {
	for (int i = 0; i < n; i++) {
		if (arr[i] != input[i]) return false;
	}
	return true;
}

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		input[i] = i;
		arr[i] = i;
	}
	for (int i = 0; i < n; i++) scanf("%d", &p[i]);
	for (int i = 0; i < n; i++) scanf("%d", &s[i]);

	int time = 0;
	bool flag = true;
	while (1) {
		if (check()) break;

		if (time > 0 && check_input()) {
			flag = false;
			break;
		}
		mix_card();
		time++;
	}
	
	if (!flag) printf("-1\n");
	else printf("%d\n", time);
	return 0;
}