1074 - Z

첫 시도

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int N, r, c;
long long ans;

void input(){
    cin>>N>>r>>c;
}


void printAnswer(){
    cout<<ans<<'\n';
}

void go(int x, int y, long long size){
    if(size==1){
        if(x==r && y==c){
            printAnswer();
            exit(0);
        }
        ans++;
        return;
    }

    // 왼쪽 위
    int move = sqrt(size)/2;
    go(x-move, y-move, size/4);

    // 오른쪽 위
    go(x-move, y, size/4);

    // 왼쪽 아래
    go(x, y-move, size/4);

    // 오른쪽 아래
    go(x, y, size/4);
}

void run(){
    go(pow(2, N)-1, pow(2, N)-1, pow(2, N)* pow(2, N));
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    if(N==1){
        cout<<0<<'\n';
    }
    else{
        run();
    }
}

문제에서 N의 최댓값은 15이므로, 탐색가능한 공간의 크기는 2^15 * 2^15 = 1073741824 ~= 10억

약 1초에 약 1억번이고, 이 문제의 제한시간이 0.5초이므로, 10억 >> 5000만이 되어서 시간초과

-> 시간을 줄여보자!

두번째 시도

#include<iostream>
using namespace std;

int N, r, c;
long long ans;

void input(){
    cin >> N >> r >> c;
}

void printAnswer(){
    cout << ans << '\n';
    exit(0);
}

void go(int x, int y, int size){
    if(size == 1){
        if(x == r && y == c){
            printAnswer();
        }
        ans++;
        return;
    }

    int half = size / 2;
    int area = half * half;

    // 현재 영역을 4분할하여 각 영역에 대해 재귀 호출

    // 왼쪽 위
    if(r < x + half && c < y + half){
        go(x, y, half);
    } else {
        ans += area;
    }

    // 오른쪽 위
    if(r < x + half && c >= y + half){
        go(x, y + half, half);
    } else {
        ans += area;
    }

    // 왼쪽 아래
    if(r >= x + half && c < y + half){
        go(x + half, y, half);
    } else {
        ans += area;
    }

    // 오른쪽 아래
    if(r >= x + half && c >= y + half){
        go(x + half, y + half, half);
    } else {
        ans += area;
    }
}

void run(){
    int size = 1 << N;
    go(0, 0, size);
}

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

정답!!

첫번째, 두번째 시도 차이점

코드 변경 점

1. pow 함수 대체
   pow(2, N) 대신 1 << N을 사용

2. 재귀 함수 수정
   go 함수에서 x, y 좌표를 시작점으로 설정하고, size를 한 변의 길이로 사용하도록 수정
   목표 위치(r,c)가 속한 영역만 재귀 호출

   그렇지 않은 영역에 대해서는 해당 영역의 크기만큼 ans에 더해줍니다.

시간 복잡도의 차이

1. 원래 코드의 시간 복잡도
   각 재귀 단계마다 4개의 재귀 호출을 수행
   재귀 깊이는 N이므로, 시간복잡도는 = O(4^𝑁)

2. 수정된 코드의 시간 복잡도
   각 재귀 단계마다 1개의 재귀 호출만 수행
   재귀 깊이는 동일하게 N
   따라서, 시간 복잡도 = 𝑂(𝑁)