[백준 21315번] 카드 섞기(파이썬)

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

21315번: 카드 섞기

처음에 문제를 읽고

이게 무슨말인지 이해가 되질 않았습니다.

카드를 섞는데

K가 왜 첫번째와 두번쨰가 있지?

 

이 문제를 다시 분해해보면

 

1. K 하나를 뽑아서 카드를 섞음

2. 근데 그걸 2번 한다.

3. 입력값은 카드를 그 2번 섞은 결과값이다.

 

이 문제에서 구현해줄 것은 

크게 두 개로 나눴습니다.

 

1. K의 경우의 수

-->일반적으로 순열,조합을 떠올리기 쉽습니다.

하지만 이 경우에는

'모든 경우'를 다 구해야합니다.

순열,조합에서는 1,2 2,1 이렇게는 되지만

1 1, 2 2 이런 조합은 되지 않습니다.

그래서 K가 될 수 있는 범위를 구하고

그 범위내에서 둘 씩 묶어줍니다.

 

2. 카드 섞기

-->저는 쌩 구현으로 시작했습니다.

먼저, 현재 배열에서

뒤에서 부터 2^k만큼을 pop해주고

앞에다가 insert해줍니다.

이 때, 옮겨준 숫자는 pre라는 리스트에 넣어줬죠.

그 뒤에는 k를 계속 2로 나누면서

pre뒤의 2^k만큼의 수를 pop하고 앞에다 넣기를 반복.

 

 

#백준 21315번 카드 섞기
from copy import deepcopy

N=int(input())

first=[i for i in range(1,N+1)]
last=list(map(int,input().split()))
#K의 범위를 알아보자
Ks=[]
num=1
while 2**num<N:
    Ks.append(num)
    num+=1
#K 조합의 모든 경우를 입력한다
case=[]
answer=[]
for i in range(len(Ks)):
    for j in range(len(Ks)):
        tmp=[]
        tmp.append(Ks[i])
        tmp.append(Ks[j])
        case.append(tmp)
#조합대로 쭉 보다
for c in case:
    #초반에는 first(1~N까지의 배열)로 넣어준다
    new=deepcopy(first)
    for now in c:
        #현재 K값만큼, 뒤에있는 걸 받고 앞으로 넣어준다
        pre=[]
        catch=2**now
        for _ in range(catch):
            pre.append(new.pop())

        for i in range(len(pre)):
            new.insert(0,pre[i])
        catch//=2
        #계속 2씩 나누면서 이전꺼에서 뒤에 있는 숫자를 규칙에 따라 받아줌
        while catch>0:
            new_pre=[]
            for _ in range(catch):
                new_pre.append(pre.pop(0))
            n=len(new_pre)
            for i in range(n):
                #해당 숫자를 찾아서 pop해주고 다시 앞에다가 insert
                p=new_pre[i]
                ind=new.index(p)
                new.pop(ind)
                new.insert(0,p)

            pre=new_pre
            catch//=2
    #만약 입력한 last와 같다면 답으로 받아준다.
    no=True
    for x in range(N):
        if not new[x]==last[x]:
            no=False
            break
    if no==True:
        answer=c
print(*answer)

 

특별한 규칙이 생각나지 않을 때는

먼저 쌩구현으로 시도하고

뒤에 시간초과등의 이슈가 생긴다면

dfs bfs 등등

다른 알고리즘을 적용해보면 좋겠다는 교훈을 얻었습니다.