[Java] BOJ1074_Z

www.acmicpc.net/problem/1074

1074번: Z

---

"만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다."

문제에 분할정복과 재귀의 힌트가 다 주어졌다. 배열의 크기가 최대 2^15 * 2^15 이므로 배열 전체를 탐색하면 당연히 시간초과가 난다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken()); //행
		int c = Integer.parseInt(st.nextToken()); //열
		func(r,c,1<<N, 0);
		System.out.println(count);
	}

	public static void func(int r, int c, int n, int startnum) {
		int temp = n/2*n/2;
		if(r==0 && c==0) {
			count = startnum;
			return;
		}
		if(r < n/2 && c < n/2) {  //1
			func(r, c, n/2, startnum);
		} else if(r < n/2 && c >= n/2) {  //2
			func(r, c-n/2, n/2, startnum+temp);
		} else if(r >= n/2 && c < n/2) {  //3
			func(r-n/2, c, n/2, startnum+temp*2);
		} else {  //4
			func(r-n/2, c-n/2, n/2, startnum+temp*3);
		}
		
	}
}

 

예제 입력 3 7 7 에서 63을 출력하기 위해

위와 같은 모습으로 3번만에 찾을 수 있다.

r과 c의 범위에 따라 어느 부분을 탐색해야할지를 잘 따져주면 쉽게 해결할 수 있다.