[백준 1074] Z (C++)

이 문제는 $N \le 15$, $0 \le r, c \lt 2^N$이므로, 모든 칸의 방문 순서를 구한다면 최악의 경우 $2^{30} \approx 10^9$이므로 시간초과가 발생한다.

따라서, r행 c열의 방문 순서를 직접 구해야하는데, 이는 반복해서 배열을 4분할해나가며 접근하게 된다. 따라서 재귀로 접근한다면, 문제를 쉽게 풀 수 있다.

방문순서는 최악의 경우에 10억 정도가 되니 int형으로 표현 가능한 범위이니 크게 신경쓰지 않아도 된다.

다만, 4분할을 한 뒤, $(r, c)$ 앞쪽에 방문한 $2^{N-1} \times 2^{N-1}$크기의 배열이 coef개라면, 해당 칸의 방문순서는 $coef \times 2^{N - 1} \times 2^{N-1}$번째 뒤임은 자명하다.

그리고, 해당 사분면에서 같은 과정을 반복해나가다보면, 방문횟수를 알 수 있다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, r, c, k = 1;

int solve(int sz, int x, int y) {
    int nsz = sz / 2, coef = (x / nsz) * 2 + (y / nsz);
    if (sz == 2) return coef;
    return nsz * nsz * coef + solve(nsz, x % nsz, y % nsz);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> r >> c;
    for (int i = 0; i < n; i++) k *= 2;
    cout << solve(k, r, c);
}