백준 21315 카드 섞기 c++ (완전탐색)

문제 출처 : 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

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 시뮬레이션

풀이

문제 이해와 구현이 조금 까다로운 완전 탐색이다.

완전 탐색이다보니, 풀이 자체는 그렇게 어렵지 않고,

구현도, 더 효율적으로 짤 생각에 이상한 답을 출력했는데, 안 좋은 습관인 거 같다.

내가 요즘 완전 탐색 문제를 푸는 이유는, 모든 탐색 문제를 완전 탐색으로 풀 수 있는지부터 시작해서,

풀 수 없다면 어떤 알고리즘을 적용할지, 범위를 어떻게 줄일지 등으로 탐색 문제 풀이를 나아가려는 연습을 하려고 하기 때문이다.

한 마디로, 특별한 스킬 없이 정직하게 풀 수 있는지 먼저 보는 것을 연습하는 것인데,

이 과정에서도 더 효율적으로 짜려는 것은, 취지에 맞지 않다.

아무튼, 2번의 2,k 섞기를 해서 나온 결과가 입력으로 주어지고, 우리는 두 개의 k를 찾아야 한다.

다시 말하면, 가능한 모든 k의 쌍에 대해 검사하여 k의 쌍으로 섞은 카드가 입력과 같다면 k의 쌍을 순서대로 출력하면 된다.

n이 5라고 할 때 처음 카드는 1 2 3 4 5이고,

1<=k이고, 2^k<=n이기 때문에, 이에 대해 가능한 k의 쌍은 

k1 = 1, k2 = 1

k1 = 1, k2 = 2

k1 = 2, k2 = 1

k1 = 2, k2 = 2

총 네 가지가 나올 수 있고,

이 네가지 쌍을 순서대로 모두 검사(카드 섞기)하여 입력 값과 같은 쌍을 찾는 것이다. 

2 개로 이루어진 쌍이기 때문에 2중 for문으로 쌍은 쉽게 찾을 수 있고, 카드 섞기 또한, 그냥 temp배열 만들고, 바꿔주면 된다.

 

코드

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

//1<=n<=1000
//1<=k
//2^k<=n
int n;
int result[1000];
int card[1000];
void mix(int range, int cnt) {
	//range = 이전에 위로 올린 카드들
	//cnt = 현재 위로 올릴 카드 개수
	int newCard[1000];
	int idx = 0;
	for (int i = range-cnt; i < range; i++) {
		newCard[idx++] = card[i];
		card[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		if (card[i] != 0) {
			newCard[idx++] = card[i];
		}
		card[i] = newCard[i];
	}
}

void solve(int k) {
	int range = n;
	for (int i = 1; i <= k + 1; i++) {
		int cnt = pow(2,k - i + 1);
		int a = 2;
		mix(range, cnt);
		range = cnt;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> result[i];
	}
	for (int k1 = 1; pow(2, k1) <= n; k1++) {
		for (int k2 = 1; pow(2, k2) <= n; k2++) {
			for (int i = 0; i < n; i++) {
				card[i] = i + 1;;
			}
			//2,k섞기 2번씩 완탐
			solve(k1);
			solve(k2);
			bool isFinish = true;
			for (int i = 0; i < n; i++) {
				if (result[i] != card[i]) {
					isFinish = false;
					break;
				}
			}
			if (isFinish) {
				cout << k1<<' '<<k2;
				return 0;
			}
		}
	}
	
	return 0;
}