🦊 카드 섞기

1. 문제 링크

21315번: 카드 섞기

2. 코드

Python3 31120KB 44ms

# 21315

def equals(arr1, arr2):
    for i in range(len(arr1)):
        if arr1[i] != arr2[i]:
            return False
    return True

# 카드를 재귀적으로 섞음
def draw(arr, i, k):
    if i == k + 2: #마지막 단계에 탈출
        return arr

    count = 2 ** (k - i + 1) # 섞을 개수
    remain = arr[:-count]
    to_draw = arr[-count:]

    return draw(to_draw, i + 1, k) + remain

# 각 K는 9 이내 (2^9 까지 가능)
N = int(input())
orders = list(map(int, input().split()))

for k in range(1, 10):
    if 2 ** k >= N:
        break
    cards = [i for i in range(1, N + 1)]
    cards = draw(cards, 1, k)
    for k2 in range(1, 10):
        if 2 ** k2 >= N:
            break
        if equals(orders, draw(cards, 1, k2)):
            print(k, k2)
            exit()

• 해설 재귀를 이용하여 카드를 섞음

  각 결과를 처음 입력과 비교하여 같으면 출력 후 종료

  2^k < N 이기 때문에 k 의 최댓값은 9로 브루트포스를 이용해도 시간초과 x