[baekjoon] 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

예제 입력

5
1 3 5 4 2

예제 출력 

2 1

풀이

카드섞이 알고리즘을 그대로 구현해서 완전탐색했다.

 

#include <iostream>
#include <cmath>

using namespace std;

//k : k의 최대값
int n, k;
int *arr, *first, *second, *third;

void print_arr(int *arr)
{
    for(int i = 0; i < n; i++)cout << arr[i] << " ";
    cout << "\n";
}

//같은지 비교
int check()
{
    for(int i = 0; i < n; i++)
    {
        if(arr[i] != third[i])return 0;
    }
    return 1;
}
void swap(int result[], int range)
{
    int size = pow(2,range);
    int *temp = new int[size];
    for(int i = 0; i < pow(2, range); i++)
    {
        temp[i] = result[i];
    }

    for(int i = 0; i < pow(2,range); i++)
    {
        int idx = i + pow(2, range);
        result[i] = result[idx];
        result[idx] = temp[i];
    }
    
}


void cardMix(int *origin, int *result, int times)
{
    int j, k;
    for(int i = times; i >= 0; i--)
    {
        if(i == times)
        {
            for(j = n - pow(2, times), k = 0; j < n; j++, k++)
            {
                result[k] = origin[j];
            }
            for(j = 0, k = pow(2,times); j < n - pow(2,times) ; j++, k++)
            {
                result[k] = origin[j];
            }
        }
        else
        {   
            swap(result, i);
        }
        //print_arr(result);
    }
}

int main()
{
    cin >> n;

    arr = new int[n];
    first = new int[n];
    second = new int[n];
    third = new int[n];

    for(int i = 0; i < n; i++)cin >> arr[i];
    for(int i = 0; i < n; i++)first[i] = i + 1;
    for(int i = 1; pow(2, i) < n; i++)k = i;

    for(int i = 1; i <= k; i++)
    {
        cardMix(first, second, i);
        for(int j = 1; j <= k; j++)
        {
            cardMix(second, third, j);
            if(check())
            {
                cout << i << " " << j;
                return 0;
            }
        }
    }

}