[BOJ] 1074. Z

재귀를 이용하여 분할정복하는 문제이다.

func(int i, int j, int size) 함수를 이용하여 size==1이 될때까지 계속 호출하는 형태로  재귀를 반복하게 된다. 기저조건은 size가 1이 될때 cnt++를 해주고 return을 한다. 재귀는 Z모양으로 4번을 호출하게 된다.

package chap06;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1074_Z {
    
    static int R,C;
    static int cnt;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        int size=1<<N;
        
        func(0,0,size);
    }
    
    static void func(int i,int j, int size) {
        if(size==1) {    //확인
            if(i==R && j==C)
                System.out.println(cnt);
//            System.out.println(i+ " ," +j + "== " +cnt);
            cnt++;
            return;
        }
        
        size=size/2;
        func(i,j,size);
        func(i,j+size,size);
        func(i+size,j,size);
        func(i+size,j+size,size);
    }
}