[백준] 21315. 카드 섞기 (python)

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

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를 출력한다.

제한

• 3 ≤ N ≤ 1,000
• 1≤ K, 2K < N

예제 입력 1

5
1 3 5 4 2

 

예제 출력 1

2 1

 

 

풀이

문제에 나온 설명대로 차근히 구현해내면 되는 문제다. 하지만 시간 초과가 걸릴 수 있어 입력 제한을 잘 살펴야 한다.

 

(2, K) 섞기 

N개의 카드 더미 중에서

첫번째 단계는 카드 더미 중 밑에서 2^k 개의 카드를 맨 위로 올린다.

i번째 단계는 첫번째 단계에서 올린 카드 더미 중 밑에서 2^(k-i+1)개의 카드를 맨 위로 올린다.

 

단계가 올라갈 수록 같은 행동이 반복되고, i단계의 결과가 (i+1)단계에서 사용되는 걸 보면

재귀가 떠오른다. 그래서 (2, k) 섞기 함수를 재귀를 통해서 구현했다.

 

1. (2, k)섞기를 2번을 하기 때문에 첫번째 k와 두번째 k가 될 수 있는 경우의 수를 2중 반복문을 이용해

   (1,1) 부터 하나씩 증가시키면서 두 번의 (2, k) 섞기를 거친다.

 

2. 두 번의 (2,k) 함수를 거친 결과가 입력으로 받았던 배열과 동일하면 그 때의 (첫번째 k, 두번째 k) 조합을 출력하고 종료한다.

 

3. (2, k) 섞기 함수

    시작하는 배열 리스트와, 단계 i, k 를 인자로 받아서

    i 가 1이면, 즉, 첫번째 단계라면 2^k 만큼,

   이외에는 2^(k-i+1) 만큼의 카드 개수를 리스트 뒤에서 잘라내어 앞으로 옮겨준다.

    => 여기서는 파이썬의 리스트 슬라이싱을 사용하면 편리하게 구현할 수 있다.

         그리고 잘라낸 카드 더미 리스트를 다음 재귀함수를 호출하는 인자로 넣어주고, 단계를 증가시킨다.

•     종료 조건

    문제에서  i(2 ≤ i ≤ K + 1)번째 단계라고 나오기 때문에 i가 K+1단계를 넘어가면 넘겨받은 리스트를 리턴하고 종료시킨다. (실제로 i가 K+1 단계를 넘어가면 카드 더미의 개수가 정수 값으로 나오지 않는다.)

 

 

4. k의 범위

   문제를 위와 같은 알고리즘으로 풀어주고 제출했을 때, 시간초과가 나왔다.

   그래서 문제를 찬찬히 살펴본 결과, 시간 초과를 피하기 위해서는 k의 범위를 잘 살펴봐야 한다.

   처음 코드에서는 k는 1부터 n-1까지 돌도록 반복문을 구현했었다.

   하지만 문제의 제한 부분을 보면

• 3 ≤ N ≤ 1,000
• 1≤ K, 2K < N

   이렇게 나와있는데, N이 1000된다면 K는 999까지 돌게 되고, 그럼 2^k 의 값을 어마무시하게 커진다.

   이러니 당연히 시간초과가 나올 수 밖에 없다.

    

    그래서 while 반복문으로 2^k 가 1000이 넘지 않도록 k의 범위를 다시 설정해주었다.

 

 

import sys
input = sys.stdin.readline
n = int(input())
after = list(map(int, input().split()))
arr = [i+1 for i in range(n)]

def bland_card(prev, i, k):
    if i > k + 1:
        return prev

    if i == 1:
        cnt = 2 ** k
    else:
        cnt = 2 ** (k-i+1)

    size = len(prev)
    next = prev[size-cnt:]
    return bland_card(next, i+1, k) + prev[:size-cnt]

def sol():
    k1 = 1
    while 2**k1 < n:
        first = bland_card(arr, 1, k1)
        k2 = 1
        while 2 ** k2 < n:
            second = bland_card(first, 1, k2)
            if second == after:
                print(k1, k2)
                return
            k2 += 1
        k1 += 1


sol()

 

 

 

+) 시간초과가 났던 코드

import sys
input = sys.stdin.readline
n = int(input())
after = list(map(int, input().split()))
arr = [i+1 for i in range(n)]

def bland_card(prev, i, k):
    if i > k + 1:
        return prev

    if i == 1:
        cnt = 2 ** k
    else:
        cnt = 2 ** (k-i+1)

    size = len(prev)
    next = prev[size-cnt:]
    return bland_card(next, i+1, k) + prev[:size-cnt]

def sol():
    for k1 in range(1, n):
        first = bland_card(arr, 1, k1)
        for k2 in range(1, n):
            second = bland_card(first, 1, k2)
            if second == after:
                print(k1, k2)
                return

sol()

 

 

알고리즘 분류

• 완전탐색
• 구현