BOJ 33371 Bit Component

문제 링크입니다.

문제 요약

$N$ 이하의 양의 정수를 이진 표현 후 세로로 나열해 격자를 만듭니다. 이때 모든 1이 하나의 연결 요소가 되도록 $N$개의 정수를 배치하는 방법을 찾으세요.

풀이

$N \le 3$에 대해서는 대충 전처리해 줍니다. 자리수가 $2$ 이하라 중간을 못 잇고 어쩌구 하는 제약이 걸리지를 않아서 따로 처리해 줘야 합니다.

$2^k \le N \lt 2^{k+1}$이라고 합시다. MSB를 연결 요소로 끌어오려면 $2^k + 2^{k-1} \lt N$이어야 함을 알 수 있습니다. 딱 $2^k + 2^{k-1}$은 왜 안 되나 싶으실 수 있는데, 이 경우 MSB가 1인 모든 수가 한 덩이로 붙어 다녀야 되는 데다가 MSB가 0인 것과 1인 것을 이을 때 $N$을 반드시 써야 해서, $2^k \cdots N-1$까지의 값들에서 MSB를 제외한 연결 요소가 $N$을 끼워넣는 시점에 연결이 끊어져 버립니다. 그래서 안 돼요. 여기서 불가능 조건을 이렇게 자세히 서술했다는 점에서 미루어 보아 분명히 이게 필요충분조건이겠네요

아무튼 그래서 나머지 경우는 해 구성이 가능합니다. $2^k-1$까지의 수를 조건을 만족하도록 배열한 순열 $p_k$와 $2^{k-1}-1$까지의 수를 조건을 만족하도록 배열한 순열 $p_{k-1}$를 이용해 순열 $p_{k+1}$을 만드는 것을 목표로 합니다. 방법은 다음과 같습니다.

• $[2^{k+1}-1, 2^k+2^{k-1}, 2^k]$를 준비합니다.
• $p_{k-1}$의 각 원소에 $2^k$를 더한 것과, $2^k+2^{k-1}$을 더한 것을 번갈아 나열합니다. 이때 $2^{k+1}-1$는 제외합니다.
• $p_k$를 그대로 그 뒤에 붙입니다.

이러한 구성 방식을 이용하면 위의 그림과 같이 1들이 단일 연결 요소를 이룸을 확인할 수 있습니다. 거기서 나아가, 두 번째 파트에서 왼쪽에서 두 번째 비트가 0인 것과 1인 것을 번갈아 두었기 때문에, 두 번째 비트가 1인 것 중 단 하나의 원소만 있어도 모든 1들이 단일 연결 요소를 이루게 됩니다. 즉 해가 존재하는 $N$에 대해서 $N$ 초과의 값을 제거하고 남은 원소들을 순서를 그대로 유지한 채 이어붙여도 여전히 1들이 단일 연결 요소를 이루는 것까지도 확인할 수 있습니다!

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<int> perm[25];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	if(n == 1) return !(cout << "YES\n1");
	if(n == 2) return !(cout << "NO");
	if(n == 3) return !(cout << "YES\n1 3 2");
	int t;
	for(int k = 2; k <= 20; k++){
		if((1<<k) <= n && n <= (1<<k)+(1<<k-1)) return !(cout << "NO");
		if(n < (1<<k+1)) t = k;
	}
	perm[2] = {2,3,1};
	perm[3] = {7,5,4,6,2,3,1};
	for(int i = 4; i <= t+1; i++){
		perm[i].push_back((1<<i)-1);
		perm[i].push_back((1<<i-1)+(1<<i-2));
		perm[i].push_back(1<<i-1);
		for(auto p : perm[i-2]){
			perm[i].push_back((1<<i-1)+p);
			if(p != (1<<i-2)-1) perm[i].push_back((1<<i-1)+(1<<i-2)+p);
		}
		for(auto p : perm[i-1]) perm[i].push_back(p);
	}
	cout << "YES\n";
	for(auto i : perm[t+1]) if(i <= n) cout << i << ' ';
}