백준[1074] - Z

문제

백준 1074 문제 보기

접근 방법

일일이 (0,0)부터 좌표를 찍는 순으로 접근하면 시간 초과를 유발한다. 따라서 좌표가 어느 위치에 있는지 확인한 뒤 해당 분면까지 계산한다. 또 다시 분할된 좌표를 기준으로 계산한다.

코드

#include <iostream>

using namespace std;

int power2(int k) {
    // 2의 제곱을 계산
    return (1 << k);
}

int divide(int n, int x, int y){
    if (n==1) {
        return 2*x+y;
    } else {
        // 좌표를 4분할 했을 때 오른쪽 위 또는 왼쪽 위에 있는지 확인
        if (x < power2(n-1)) {
            if (y < power2(n-1)) {
                // 왼쪽 위
                return divide(n-1, x, y);
            } else {
                // 오른쪽 위
                return divide(n-1, x, y-power2(n-1)) + power2(2*n-2);
            }
        } else {
            if (y < power2(n-1)) {
                // 왼쪽 아래
                return divide(n-1, x-power2(n-1), y) + power2(2*n-2)*2;
            } else {
                // 오른쪽 아래
                return divide(n-1, x-power2(n-1), y-power2(n-1)) + power2(2*n-2)*3;
            }
        }
    }
}

int main(){
    int n, x, y;

    cin >> n >> x >> y;
    cout << divide(n, x, y) << '\n';

    return 0;
}