🐹 카드 섞기

1. 문제 링크

21315번: 카드 섞기

2. 코드

PyPy3 208848KB 2860ms

from itertools import product

def shuffle(k):
    global cards
    # 1단계 섞기
    left = cards[:N-2**k]
    main_cards = cards[N-2**k:]
    # 나머지 섞기
    for i in range(2, k + 2):
        l = len(main_cards)
        left = main_cards[:l-2**(k-i+1)] + left
        main_cards = main_cards[l-2**(k-i+1):]
    
    return main_cards + left
        
N = int(input())
end_cards = list(map(int, input().split()))
k_cases = [i for i in range(1, N+1)]

for first, second in product(k_cases, repeat=2):
    cards = [i for i in range(1, N+1)]
    cards = shuffle(first)
    cards = shuffle(second)
    if cards == end_cards:
        print(first, second)
        break

3. 해설

한 번 카드를 섞을 때마다 가장 최근에 섞은 카드 범위를 main_cards에 저장해 둔 후 남은 카드들을 남겨준 순서대로 합친다. (이때 남겨진 순서가 오래 된 순서일 수록 뒤쪽에 자리한다)

1부터 N까지의 가능한 모든 경우를 중복순열로 처리하여 두 번 섞는 모든 경우를 구한다.

모든 경우로 2번 섞어본 후 최종 카드 순서가 동일한 경우의 k를 출력한다.