BOJ 33804 Cute Matrix
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
길이 $3$의 등차수열을 찾을 수 없는 크기 $N$의 스도쿠를 찾으세요. 가로나 세로로만 안 겹치면 됩니다.
풀이
$N = 1$일 때는 당연히 됩니다. 그리고, 이외의 홀수는 안 돼요.
적당히 $N = 7$이라고 해보겠습니다. 그러면 $4$가 가운데로 들어가는 행에서 $147, 246, 345$가 모두 나오지 않게 만들어야 합니다. 이를 위해서는 $17, 26,35$가 각각 $4$의 왼쪽이나 오른쪽 중 한 곳으로 몰아서 들어가야 하는데, $4$의 양옆으로는 각각 $3$칸으로 홀수 개의 칸이 있어 불가능합니다. 이 논의를 확장하면 임의의 음이 아닌 정수 $k$에 대해 $N = 4k+3$ 꼴인 모든 경우가 불가능함을 보일 수 있습니다.
$N = 9$인 경우는 어떤가요. 이때는 $5$를 가운데가 아니고 한 칸 옆에 두어서, 양옆에 남는 칸이 각각 $3$칸, $5$칸으로 홀수가 되도록 만듭니다. 이러면 이전과 같은 논의를 거쳐 임의의 양의 정수 $k$에 대해 $N = 4k+1$인 경우 역시 불가능함을 보일 수 있습니다. 1이 포함되지 않음에 유의합시다!
다음으로 양의 정수 $k$와 $3$ 이상의 홀수 $p$에 대해 $N = 2^k p$ 꼴일 때 불가능함을 보입시다. $2$번 열에 $2^{k-1}p$가 들어 있는 행을 잡읍시다. $(2^{k-1}p-1, 2^{k-1}+1)$부터 $(1,2^k-1)$까지의 쌍이 각각 $2^{k-1}p$에 대해 한쪽으로 몰아넣어져야 하기 때문에, 1번 열에는 이중 어느 쌍에도 속하지 않는 $2^k p$만이 유일하게 들어갈 수 있습니다.
이때 $2^{k-1}x$ $(p \le x \le 2p)$ 꼴의 원소 총 $p+1$개에 주목합시다. 이를 각각 $0$부터 $p$까지의 정수로 바꾸어도 자기들끼리의 등차수열 존재 여부는 같기 때문에 이와 같이 변형하고 생각해 봅시다. 그러면 첫 두 원소가 각각 $0$과 $p$이고, 그 뒤에 $1$ 이상 $p-1$ 이하의 원소를 적절히 채워넣을 수 있는지 확인해 보면 됩니다. 그런데 $0$은 짝수, $p$는 홀수이므로, $1$ 이상 $p-1$ 이하의 모든 원소에 대해 $0$과 $p$ 중 하나는 홀짝성이 같아, 그 두 원소의 등차중항이 마찬가지로 $1$ 이상 $p-1$의 원소 중 존재합니다.
등차수열을 만들기 않기 위해 등차중항에 해당하는 원소는 우리가 확인한 원소보다 뒤에 배치되어야 합니다. 이를 화살표의 형식으로 나타내면 자신에게로 되먹여지는 화살표가 없는 (즉, $f(x) = x$인 $1 \le x \le p-1$가 없는) 함수형 그래프가 얻어지며, 길이가 $2$ 이상인 사이클이 반드시 존재하게 됩니다. 어떤 원소가 더 오른쪽에 있어야 한다는 정보가 순환하므로 이는 모순입니다. 따라서 $N = 2^k p$의 경우에도 불가능함을 알 수 있습니다.
남은 경우는 $N = 2^k \ (k \ge 0)$일 때뿐입니다. 이 때는 해 구성이 가능합니다!
편의 상 각 행렬의 원소를 $1$ 이상 $N$ 대신 $0$ 이상 $N$ 미만이라고 생각합시다. 이제 귀납적으로 보입시다. $N = 1$일 때는 자명하게 가능하므로, $N = 2^k$가 가능할 때 $N = 2^{k+1}$ 역시 가능함을 보이는 것으로 충분합니다. $2^{k+1} \times 2^{k+1}$ 크기의 행렬을 가로 세로로 반씩 쪼개 $2^k \times 2^k$ 크기의 행렬 $4$개를 만듭니다. 각각의 행렬에 홀수 또는 짝수를 몰아넣으면, 전체 행렬의 각 행 또는 열의 가운데를 지나가도록 원소 셋을 고르면 원소의 홀짝성 배치가 (홀, 홀, 짝)과 같은 형태로만 나타나므로 등차수열이 생기지 않습니다. 따라서 각 $2^k \times 2^k$ 크기의 행렬이 귀여운 행렬이면 전체 행렬도 귀여운 행렬이고, 각 원소를 반으로 나누면 $N = 2^k$인 상황이 되므로 가정에 의해 귀여운 행렬을 만들 수 있습니다. 따라서 $N = 2^k$ 꼴일 때는 항상 가능합니다.
재귀적으로 구현해도 좋고, 재귀적인 구현이 실제로는 XOR 테이블에서 비트열을 뒤집은 형태를 구하는 것임을 추가적으로 관찰해서 구현량을 줄일 수도 있습니다. 재귀적인 구현은 제 대회 후기에서 확인할 수 있어요. 아래는 구현량을 좀 줄인 버전입니다. 시간 복잡도는 어느 쪽이든 ${\cal O}(N^2 \lg N)$입니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n; cin >> n; int k = 0; while((1<<k) < n) k++;
if(n != (1<<k)) return !(cout << 0);
cout << 1 << '\n';
for(int i = 0; i < n; i++, cout << '\n') for(int j = 0; j < n; j++){
int t = i^j; int ans = 0;
for(int bit = 0; bit < k; bit++){
ans <<= 1; ans |= t&1; t >>= 1;
}
cout << ans+1 << ' ';
}
}