(BOJ) 1074 풀이

#include<bits/stdc++.h>

using namespace std;
int N,r,c,answer=0;
void Z(int N,int x,int y,int value){
    // cout << "Z(" <<N<<','<<x<<','<<y<<','<<value<<")\n";
    if(x==r&&y==c){
        answer=value;
        return;
    }
   if(x<=r&&r<x+N&&y<=c&&c<y+N){
       Z(N/2,x,y,value); // 1사분면
       Z(N/2,x,y+N/2,value+(N/2)*(N/2)); // 2사분면
       Z(N/2,x+N/2,y,value+(N/2)*(N/2)*2); // 3사분면
       Z(N/2,x+N/2,y+N/2,value+(N/2)*(N/2)*3); // 4사분면
   }
}
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N >> r >> c;
    Z(1<<N,0,0,0);
    cout << answer << '\n';
}

재귀함수는 좀 어려운 것같다.

먼저 base condition 은 x,y == r,c 일 때이다.

재귀함수 원형

N : 현재 구역 변의 크기

x : 행

y : 열

value : (x,y) 에 있는 값

N==2 일 때의 2차원 배열이다.

재귀함수는 0,0 부터 시작해서 크기를 2씩 나누면서 r,c 가 속해있는 사분면을 크기가 1이 될 때까지 재귀함수를 호출한다.

N==2 일 떄 크기 (변의 길이) 는 $2^N$ 이다.

조건문에서 r,c 가 현재 구역에 속하지 않으면 함수를 호출하지 않고 종료해 시간을 절약할 수 있다.

 

최초호출에서는 모든 사분면에 대해 함수를 호출하지만,

각 호출된 함수에서는 (r,c) 가 자신의 구역에 없으면 그냥 리턴한다.

 

물론, 각 사분면마다 if 문으로 범위체크를 하면 시간을 더 절약할 수 있긴한데 코드가 예쁘지않다

 

 

value 값이 답과 직결되는 부분인데, 규칙이 있다.

현재 크기(N)는 4이고 , 제 1,2,3,4 사분면에 있는 가장 작은 값은 4,0,8,12 이다.

제 1사분면 : $(N/2)^2*1$ == 4

제 2사분면 : $(N/2)^2*0$ == 0

제 3사분면 : $(N/2)^2*2$ == 8

제 4사분면 : $(N/2)^2*3$ == 12

위와 같은 규칙을 찾을 수 있다.

 

하지만 N/2 를 하고 (3,1) 이 속해있는 3사분면에서 탐색할 때,

Z(2,2,0,8) 이렇게 함수가 호출되는데

최초 호출이 아닌 이렇게 쪼개져서 호출될 때는, 저 곱한값 에 base 가 되는 value 값 (여기서는 8) 을 더해줘야한다.

그러면 정확한 규칙은 아래와 같다.

제 1사분면 : $(N/2)^2*1+value$

제 2사분면 : $(N/2)^2*0+value$

제 3사분면 : $(N/2)^2*2+value$

제 4사분면 : $(N/2)^2*3+value$