[BOJ] 1074번 Z

풀이

이분탐색으로 범위를 4등분으로 나눠가면서 각 사사분면의 맨 처음 원소를 기준으로 큰 사각형에서 작은 사각형으로 들어간다. 계속 4등분으로 들어가면 최소단위까지 들어가면 된다. 새로운 사사분면으로 갈 때, 즉 범위를 분할 할 때 범위의 값도 계산한다.

코드

import java.util.Scanner;

/**
 * Z
 */
public class Main_1074_이광용 {

	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();
		int c = sc.nextInt();
		
		int x = 0, y = 0;
		int ans = 0; //사사분면을 행 과 열로 나눠서 각각 결정될때마다 
		
		int length = 1; //한 변의 길이
		for(int i = 1 ; i <= n; i ++) {
			length = length * 2;
		}
		//한 사사분면에 몇개? 
		
		
		for(int k = 0; k < n; k++) {
			length /= 2; //4 
			if(r >= x + length) { //행 범위 좁히기 -> 조건 만족하면 3 or 4분면
				x += length;
				//처음 1분면 첫 인덱스에서 최소한 3분면 첫 인덱스로 간다는 것을 의미함. (0,0) = 0 -> (4, 0) = 32
				ans += length * length * 2;
			}
			if(c >= y + length) { //열 범위 좁히기 -> 조건 만족하면 2 or 4분면
				y += length;
				//조건 만족하면 x의 위치와 상관없이 한 분면 옆으로 간다는 것을 의미
				ans += length * length;
			}
			if(x == r && y == c) break;
		}
		System.out.println(ans);
	}

}

재귀로 푼 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_1074{
    static int r;
    static int c;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int N = Integer.parseInt(inputs[0]); //2^N*2^N 을 만들기 위한 입력
        r = Integer.parseInt(inputs[1]); //r,c 입력
        c = Integer.parseInt(inputs[2]);
        
        int pow_n = (int) Math.pow(2, N);


        recursive(0,0, pow_n, 0);

    }

    
   /**
    * 
    * @param si : 시작 i
    * @param sj : 시작 j
    * @param length : 시작점부터 해당 범위까지의 길이
    * @param cnt : (si,sj)순서
    */
    public static void recursive(int si, int sj, int length, int cnt){ 
    	// 2는 쪼갤 수 있는 단위의 최소(사각형 길이의 최소)
    	// 1은 완전히 다 쪼개진 상태
    	if(length==1){
            for (int i = si; i <= si+length; i++) {
                for (int j = sj; j <= sj+length; j++) {
                    if(i==r && j==c){
                        System.out.println(cnt);
                        return;
                    }
                    cnt++;
                }
            }
            return;
        }

        int half = length/2;

        //4개의 범위 중 r,c가 속한 범위로 들어감
        if(si<=r && r<si+half && sj<=c && c<sj+half){ 
            recursive(si, sj, half, cnt);
        }else if(si<=r && r<si+half && sj+half<=c && c<sj+length){
            recursive(si, sj+half, half, cnt+half*half);
        }else if(si+half<=r && r<si+length && sj<=c && c<sj+half){
            recursive(si+half, sj, half, cnt+half*half*2);
        }else{
            recursive(si+half, sj+half, half, cnt+half*half*3);
        }
    }
}