문제 출처: https://www.acmicpc.net/problem/1074
문제
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int answer = 0;
private static int[][] arr = {
{ 0, 1 },
{ 2, 3 },
};
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int r = Integer.parseInt(tokenizer.nextToken());
int c = Integer.parseInt(tokenizer.nextToken());
recursiveCall(N, r, c);
System.out.println(answer);
}
private static void recursiveCall(int N, int i, int j) {
if (N == 1) {
answer += arr[i][j];
return;
}
int center = 1 << (N - 1);
int right = 1 << ((N - 1) * 2);
int bottom = 1 << ((N - 1) * 2 + 1);
// 좌표의 위치 찾기
if (i < center && j >= center) {
// 1사분면
j -= center;
answer += right;
} else if (i < center && j < center) {
// 2사분면
} else if (i >= center && j < center) {
// 3 사분면
i -= center;
answer += bottom;
} else {
// 4 사분면
i -= center;
j -= center;
answer += right + bottom;
}
recursiveCall(N - 1, i, j);
}
}