카드 섞기
문제
마술사 영재는 카드 더미를 이용한 마술을 개발하였다.
카드들에는 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;
}
}
}
}
'알고리듬 > 문제' 카테고리의 다른 글
[baekjoon] 1194 (0) | 2023.04.10 |
---|---|
[baekjoon] 12100 (0) | 2023.03.23 |
[baekjoon] 14502 (0) | 2023.03.21 |
[baekjoon] 16234 (0) | 2023.03.20 |
[baekjoon] 1090 (0) | 2023.03.18 |