백준 1074 C++

#include <iostream>

using namespace std;

// N은 배열의 크기인 2^N, (r, c)는 찾아야 할 좌표
int N, r, c;

// 현재 탐색 중인 부분 배열의 왼쪽 위 좌표 (x, y), ans는 현재까지 탐색한 칸의 수
int x, y, ans;

// 재귀적으로 분할정복을 수행하는 함수
void solve(int x, int y, int n) {

    // 찾아야 할 좌표 (r, c)에 도달했을 때 현재까지의 탐색 칸의 수를 출력하고 함수 종료
    if (x == r && y == c) {
        cout << ans << "\n";
        return;
    }

    // 현재 탐색 중인 부분 배열이 (r, c)를 포함하면 4분할하여 재귀적으로 탐색
    if (r < x + n && r >= x && c < y + n && c >= y) {
        solve(x, y, n / 2);  // 왼쪽 위칸
        solve(x, y + n / 2, n / 2);  // 오른쪽 위칸
        solve(x + n / 2, y, n / 2);  // 왼쪽 아래칸
        solve(x + n / 2, y + n / 2, n / 2);  // 오른쪽 아래칸
    }
    // (r, c)가 현재 탐색 중인 부분 배열에 속하지 않으면 현재 탐색한 칸의 수만큼 더해줌 (탐색한 것으로 간주)
    else {
        ans += n * n;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> r >> c; // 배열의 크기 N과 찾아야 할 좌표 (r, c)를 입력으로 받음

    solve(0, 0, (1 << N)); // 초기 상태에서 전체 배열을 탐색하는 함수 호출

    return 0;
}