[BOJ/Python] 백준 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를 출력한다.

풀이

import math
# 시간 초과...
n = int(input())
li = list(map(int, input().split()))

def shuffle(card, idx):
    if idx == 0:
        return card
    div_card = card[len(card)-idx:]
    # 올리는 카드의 개수가 두배씩 줄어듬
    return shuffle(div_card, idx//2) + card[:len(card)-idx]

card_li = [i for i in range(1, n + 1)]
# for k1 in range(1, n + 1): # 1024 미만이어야 하니까 단순하게 9로 잡고 했다가 틀림 ..
#     for k2 in range(1, n + 1):
#         if shuffle(shuffle(card_li, 2 ** k1), 2 ** k2) == li:
#             print(k1, k2)

# 여기부터 구글링
m = int(math.log2(n)) # 생각해보니 모든 범위에서 9까지 돌면 안되긴 하다;
ans = []
for k1 in range(1, m + 1):
    for k2 in range(1, m + 1):
        if shuffle(shuffle(card_li, 2 ** k1), 2 ** k2) == li:
            ans.append((k1, k2))
print(*ans[0]) # 중복값이 있을 때 처리..

 

• 섞는 카드 더미의 수는 2^(n - i + 1)개이므로, 단계를 거듭하면서 인덱스가 2배씩 줄어든다.
• 섞는 카드의 수를 위로 올리고, 남는 카드를 뒤에 붙여주는 방식으로 재귀 함수 구성
• 2번 섞는 경우의 모든 경우의 수를 돌면서 입력값과 일치하는 경우 k1, k2를 출력했다.
• 근데 n회만큼 돌렸더니 너무 많이 돌아서(,,) 2^n인 1024보다 섞기 수가 작아야 하므로, 냅다 9로 박았다가 실패했다 -> 1000보다 작은 수는 9회 돌리면 안된다...
• 찾아보니까 math 라이브러리를 가져와서 로그처리 해준 후에 반복문을 돌리는 방식으로 값을 구했다.