🐢 카드 섞기

1. 문제 링크

21315번: 카드 섞기

2. 코드

PyPy3 110404KB 112ms

"""
[21315] 카드 섞기

💛 문제
마술사 영재는 카드 더미를 이용한 마술을 개발하였다.
카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다.

영재는 마술을 위해 (2, K) - 섞기를 만들었다.
(2, K) - 섞기는 총 K + 1개의 단계로 이루어져있다.
첫 번째 단계는 카드 더미 중 밑에서 2K개의 카드를 더미의 맨 위로 올린다.
이후 i(2 ≤ i ≤ K + 1)번째 단계는 직전에 맨 위로 올린 카드 중 밑에서 2K - i + 1개의 카드를 더미의 맨 위로 올린다.

예를 들어, 카드의 개수가 5개 일 때 초기 상태에서 (2, 2) - 섞기를 하는 과정은 다음과 같다.
(괄호 내에서 왼쪽에 있을수록 위에 있는 카드이다.)
(1, 2, 3, 4, 5) → (2, 3, 4, 5, 1) → (4, 5, 2, 3, 1) → (5, 4, 2, 3, 1)
영재의 마술은 상대방이 초기 상태에서 (2, K) - 섞기를 2번 한 결과를 보고 2번의 (2, K) - 섞기에서 K가 각각 무엇인지 맞추는 마술이다.

마술 아이디어는 생각했지만, K를 알아내는 방법을 모르는 영재를 위해 K를 알아내는 프로그램을 만들자.
2번의 (2, K) - 섞기 후의 카드 더미 결과를 만드는 각각의 K는 유일함이 보장된다.

💚 입력
첫 줄에 N이 주어진다.
둘째 줄에 2번의 (2, K) - 섞기 후의 카드 더미가 위에 있는 카드부터 공백으로 구분하여 주어진다.

💙 출력
첫 번째 K와 두 번째 K를 출력한다.
"""

# n개의 카드,
# 쌍을 순서대로 모두 검사(카드 섞기)하여 입력 값과 같은 쌍을 찾는 것

import math
n = int(input())
array = list(map(int, input().split()))

def card_shuffle(cardlist, index):
    if index == 0:
        return cardlist
    divided = cardlist[len(cardlist)-index:]
    return card_shuffle(divided, index//2) + cardlist[:len(cardlist)-index]


result = []
# 2^(k-i+1)개의 카드를 더미의 맨 위로 올린다
M = int(math.log2(n))
for k1 in range(1, M+1):
    for k2 in range(1, M+1):
        cards = [i for i in range(1, n+1)]
        if card_shuffle(card_shuffle(cards, 2**k1), 2**k2) == array:
            result.append((k1, k2))

print(*result[0])

• 해설