(Python) - BOJ(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] 에게 보내야한다.

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

 

 

 

---

• 풀이 :

P가 [0,1,2] * (N/2)와 같아질 때까지 규칙에 따라 카드 자리 바꿈을 실시한다.

여기서 -1을 출력하는 조건은 

가장 처음 카드 순서를 저장해두고, 카드 섞기를 진행하다가 첫 번째 카드 순서와 똑같아지는 경우 무의미한 반복이 진행되므로 이 때 -1을 출력하고 종료한다.

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
N = int(input())
P = list(map(int,input().split()))
S = list(map(int,input().split()))
ans = 0
first = P.copy()
 
while [0,1,2]*(N//3) != P:
    tmp = [0]*N
    for i in range(N):
        tmp[S[i]] = P[i]
    if first == tmp:
        ans = -1
        break
    ans += 1
    P = tmp
print(ans)