[백준][python]21315 카드 섞기

문제

https://www.acmicpc.net/problem/21315

소스코드

import sys
import math
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    card = [i for i in range(1,n+1)]
    res = list(map(int,input().split()))
    k = int(math.log2(n)) #최대 가능한 k의 값
    klist = [] #가능한 k 리스트

    def dfs(l,param_list):
        if l == 2:
            if param_list == res:
                for i in klist:
                    print(i,end=' ')
                exit()
            return
        for kk in range(1,k+1): #가능한 k의 값 
            front_list = param_list[:] #바꿀 카드 리스트
            total_list = param_list[:] #전체 카드 리스트
            for i in range(1,kk+2): #1부터 k+1번 카드 섞기 (kk+2해야 kk+1번이 됨)
                front_list = front_list[(2**(kk-i+1))*(-1):] #문제에서 주어진 갯수 만큼 앞쪽으로
                rear_list = [r for r in total_list if r not in front_list] #전체에서 섞은 카드 제외하고 뒤로 보내기
                total_list = front_list + rear_list #하나로 섞기
            klist.append(kk) #다 섞었다면 klist에 넣기
            dfs(l+1,total_list) 
            klist.pop()

    dfs(0,card[:])

설명

(2,K) 마술을 2번 한다.

가능한 K를 DFS를 이용해서 중복 포함 2개의 K를 구해준다

이때 가능한 K의 경우는 1부터 log2n 까지이다. (문제에서 2**k < n 이라고 주어짐)

2개의 K를 구했으면 K+1번 카드를 섞는다.

카드를 섞고 최종 카드가 주어진 카드와 같다면 K값을 출력해준 후 종료해준다(exit, 반드시,, 안그러면 다른 경우의 수도 체크됨)

 

 

 

후기

• 문제를 처음에 잘 이해를 못했다. 바꾼 카드 중에서 2K - i + 1 개를 앞으로 이동해야한다.
• exit을 안해줘서 시간을 너무 많이 잡아먹었다