BOJ 1074 c++

백준 1074 Z c++

 

재귀 문제.

 

(half, half)를 기준으로 1, 2, 3 ,4 분면으로 나눌 수 있음.

1->2->3->4 분면 순서대로 방문함.

 

half는 2의 n - 1승(사각형의 한 변)을 의미.

2사분면은 half * half + 1사분면에 있을 경우의 위치.

3사분면은 2 * half * half + 1사분면에 있을 경우의 위치.

4사분면은 3 * half * half + 1사분면에 있을 경우의 위치.

 

#include <bits/stdc++.h>
using namespace std;
int n, r, c;

int z(int n, int r, int c) {
    if (n == 0)
        return 0;
    int half = 1 << (n - 1);
    if (r < half && c < half)
        return z(n - 1, r, c);
    else if (r < half && c >= half)
        return half * half + z(n - 1, r, c - half);
    else if (r >= half && c < half)
        return 2 * half * half + z(n - 1, r - half, c);
    else
        return 3 * half * half + z(n - 1, r - half, c - half);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> r >> c;
    cout << z(n, r, c);
    return 0;
}