[백준 1074번 Z - Java] [분할 정복]

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

1074번: Z

 

문제

 

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

입력

 

첫째 줄에 정수 N, r, c가 주어진다.

 

출력

 

r행 c열을 몇 번째로 방문했는지 출력한다.

 

예제 입출력

 

입력	출력
2 3 1	11
3 7 7	63

 

풀이[Java]

 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String tmp[] = sc.nextLine().split(" ");
		int N = Integer.parseInt(tmp[0]);
		int x = Integer.parseInt(tmp[1]);
		int y = Integer.parseInt(tmp[2]);
		
		z(x, y, N - 1);
		
		System.out.println(answer);
	}
    
    	public static void z(int x, int y, int N) {
		if (N < 0) return;
		
		int mid = (int) Math.pow(2, N);
		int base = (int) Math.pow(4, N);
		if (x < mid) {
			if (y < mid) {//1사분면
			} else if (y >= mid) {//2사분면
				y -= mid;
				answer += base;
			}
		} else if (x >= mid) {
			if (y < mid) {//3사분면
				x -= mid;
				answer += (base * 2);
			} else if (y >= mid) {//4사분면
				x -= mid;
				y -= mid;
				answer += (base * 3);
			}
		}
		
		z(x, y, N - 1);
	}