[C++] 백준 21315: 카드 섞기

문제

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

 

 

 

풀이

• 카드를 섞는 magic(int k) 함수를 구현
• 가등한 모든 (k1, k2) 에 대해 magic을 호출해 주어진 카드 순서를 만들 수 있는지를 확인

구체적인 구현은 코드의 주석에서 확인할 수 있다.

 

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int n;
int result[1001];
int arr[1001];

void magic(int k){
    int m_arr[1001]= {};
    int n_k =1;
 
    for(int i=0; i<k; i++) n_k*=2;

    // 처음 뒤에서 k개를 앞으로 , 앞에 있던 것은 뒤로 
    for(int i=n - n_k, j=0; j<=n_k; i++, j++){
        m_arr[j] = arr[i];
    }
    for(int i = 0, j =n_k ; i<n - n_k+1; i++, j++){
        m_arr[j] = arr[i];
    }
 
    // 이후 i 번째 단계
    while(n_k>1){
        int cur_arr[1001] = {};
        int cur_k = n_k/2;
        
        // 0 부터 n_k-1 까지 중 뒤에서 cur_k 만큼 앞으로 빼기 
        for(int i = n_k - cur_k , j=0; i <=n_k-1; i++, j++){
            cur_arr[j] = m_arr[i];
        }
        
        // 0부터 n_k-1 까지 중 앞에서 남은 수만큼 뒤에 이어붙이기 
        for(int j = cur_k, i = 0; i<n_k - cur_k; i++, j++){
            cur_arr[j] = m_arr[i];
        }
        
        // 이후 숫자 이어붙이기 
        for(int j = n_k, i=n_k; j<n; j++, i++){
            cur_arr[j] = m_arr[j];
        }

        // 출력 
        for(int i=0; i<n; i++){
            m_arr[i] = cur_arr[i];
        }
        
        // n_k 줄임 
        n_k /=2;
    }

    // 배열 붙여넣기 
    for(int i=0; i<n; i++){
        arr[i] = m_arr[i];
    }
    return;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){ 
        cin >> result[i];
         arr[i] = i+1;
    }

    int max_k = log2(n);
    for (int k1 = 1; k1 <= max_k; ++k1) {
        for (int k2 = 1; k2 <= max_k; ++k2) {
            // k1, k2 사용
            magic(k1);
            magic(k2);
            
            int isSame=1;
            // 배열 검사 
            for(int i=0; i<n; i++){
                if(arr[i] != result[i]){
                    isSame = 0;
                    break;
                }
            }
            
            if(isSame == 1){
                cout << k1 << " " << k2 << "\n";
                return 0;
            }
            
            // 배열 초기화 
            for(int i=0; i<n; i++){
                arr[i] = i+1;
            }
        }
    }
    return 0;
}