[C] 1074: Z

맨 처음 생각했던건 이차원 배열 graph[40000][40000]을 잡고 돌아다니면서 수를 저장하여 r행 c열을 몇번째로 방문했는지를 확인하는 거였다. 하지만 이렇게 할 경우 512MB라는 메모리 제한에 걸리게 된다.

 

따라서 DecideSquare이라는 함수를 만들어서 r행 c열까지 재귀적으로 가는 동안 4가지 사각형 중 어디로 가야할지를 정하게 된다면 탐색에 걸리는  시간 뿐만 아니라 메모리도 아끼게 된다. 

 

여기서 주의해야할점은 재귀 함수를 쓸때 각 조건을 잘 살펴야하고 언제 return을 해야하는지를 잘 생각해야한다.

그리고 pow()를 쓸때는 double형 변수를 써야한다!

#include <stdio.h>
#include <math.h>

void recursion(double n,int x,int y,int x_target,int y_target);
int cnt=0;

void DecideSquare(double n,int x,int y,int x_target,int y_target) //어느 4분면으로 갈지 결정
{
  if(x_target<x+n/2 && y_target<y+n/2)
    recursion(n/2,x,y,x_target,y_target);
  else if(x_target>=x+n/2 && y_target<y+n/2)
  {
    cnt+=n*n/4;
    recursion(n/2,x+n/2,y,x_target,y_target);
  }
  else if(x_target<x+n/2 && y_target>=y+n/2)
  {
    cnt+=n*n*2/4;
    recursion(n/2,x,y+n/2,x_target,y_target);
  }   
   else
   {
     cnt+=n*n*3/4;
     recursion(n/2,x+n/2,y+n/2,x_target,y_target);
   }
    
}

void recursion(double n,int x,int y,int x_target,int y_target) //만족하는 좌표를 찾았는가!
{
  if(n>=2) // 더 줄어들 수 있음
  {
    DecideSquare(n,x,y,x_target,y_target);    
  }
  else
  {    
    printf("%d",cnt);
    return; 
  }  
}

int main(void)
  {
    int y,x;
    double n;
    scanf("%lf %d %d",&n,&y,&x);
    n=pow(2,n);    
    
    DecideSquare(n,0,0,x,y);       
    
  }