[백준] 1074* Z (골드5)

https://www.acmicpc.net/problem/1074

재귀 없이 규칙을 찾아보려고 1시간 동안하였지만 실패
=> 4등분하는 재귀로 풀이

package ct.baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class n1074 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int size = (int)Math.pow(2,n); // 한 변의 길이

        int ans = z(r,c, size);
        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

    static int z(int x, int y, int s){
        if(s == 1) return 0;
        int half = s/2;

		// 앞에 값들 더하기
        if(x<half && y<half){ //2사분면
            return z(x, y, half);
        }
        else if(x<half && y>=half){ //1사분면
            return half*half + z(x,y-half, half);
        }
        else if(x >= half && y<half){ //3사분면
            return 2*half*half + z(x-half, y, half);
        }
        else { //4사분면
            return 3*half*half + z(x - half, y - half, half);
        }
    }
}

==

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    static int N, r, c, ans;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); // 2^N
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        
        // N 을 가로 세로 길의를 표현하는 N 변경
//      N = (int) Math.pow(2, N);
        N = 1 << N;
        
        // 분할 정복
        // N x N 크기의 배열 영역을 4등분해서 r,c 가 어느 위치에 있는 지 확인
        // 해당 위치의 4등분 중 미리 계산이 가능한 영역은 계산, 4등분 영역 중 rc 가 있는 영역을 새로운 영역으로 만들고 
        // 원점을 이동, N = N / 2 
        
        // 원점
        int y = 0;
        int x = 0;
        
        while(true) {
            if( N == 1 ) break;
            
            // 4등분
            N /= 2;
            
            if( r < y + N && c < x + N ) { // 왼쪽 위
                ;
            }else if( r < y + N && c >= x + N ) { // 오른쪽 위
                ans += N * N * 1;
                x += N;
            }else if( r >= N && c < x + N ) { // 왼쪽 아래
                ans += N * N * 2;
                y += N;
            }else { // 오른쪽 아래
                ans += N * N * 3;
                y += N;
                x += N;
            }
        }
        
        System.out.println(ans);
    }
}

=>

	static void z(int y, int x) {
        // 기저 조건
        if( N == 1 ) return;
        
        // 4등분
        N /= 2;
        
        if( r < y + N && c < x + N ) { // 왼쪽 위
            z(y, x);
        }else if( r < y + N && c >= x + N ) { // 오른쪽 위
            ans += N * N * 1;
            z(y, x + N);
        }else if( r >= N && c < x + N ) { // 왼쪽 아래
            ans += N * N * 2;
            z(y + N, x);
        }else { // 오른쪽 아래
            ans += N * N * 3;
            z( y + N, x + N);
        }       
    }

->
9/18 완

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N,r,c, cnt;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        System.out.println(z(r,c,(int)Math.pow(2,N)));
    }

    static int z(int x, int y, int size){
//        System.out.println("start"+x+","+y);
        if(size==1) return cnt;
        int mid = size/2;

        if(x<mid && y<mid){
//            System.out.println("1s");
            z(x,y, mid);
        } else if(x<mid && y>=mid){
//            System.out.println("2s");
            cnt +=mid*mid;
            z(x,y-mid, mid);
        } else if(x>=mid && y<mid){
//            System.out.println("3s");
            cnt +=mid*mid*2;
            z(x-mid,y,mid);
        } else{
//            System.out.println("4s");
            cnt +=mid*mid*3;
            z(x-mid,y-mid,mid);
        }
        return cnt;
    }
}