[백준] 1074번

처음에는 dfs로만 해결하다가 역시나 메모리초과가 되었다.

거의 날을 새고 있어서 머리가 안돌아가서 3시간 고민 후에, claude에게 조언을 얻었는데, 필요한 범위만 챙기고 나머지는 버리라는 것이다.

 

즉, 정사각형이니까 절반씩 나누면 좌표처럼 1,2,3,4 사분면으로 볼 수 있고 이를 선택함으로써 해결이 가능하다는 것이 이 문제의 핵심이다.

#include <iostream>

int partDFS(int n, int r, int c);

int main() {
    int N, r, c;
    std::cin >> N >> r >> c;
    std::cout << partDFS(N, r, c) << std::endl;
    return 0;
}


int partDFS(int n, int r, int c) {
    if (n == 0) {
        return 0;
    }

    int half = 1 << (n-1);
    int area = half * half;
    if (r < half && c < half) { // 1 사분면
        return partDFS(n - 1, r, c);
    } else if (r < half && c >= half) { // 2 사분면
        return area + partDFS(n - 1, r, c-half);
    } else if (r >= half && c < half) { // 3 사분면
        return area*2 + partDFS(n - 1, r-half, c);
    } else if (r >= half && c >= half) { // 4 사분면
        return area*3 + partDFS(n - 1, r-half, c-half);
    }
}