문제

한수는 크기가 2의 N승 × 2의 N승인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2의 N-1승 × 2의 N-1승으로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

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

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

제한
1 ≤ N ≤ 15
0 ≤ r, c < 2의 n승

접근

처음 접근한 방식은 (0,0)부터 (r,c)까지 모든 점을 순서대로 방문하며 카운팅을 해주고, (r,c)에 도착했을때의 카운트를 출력하는 형태로 재귀함수를 짰으나, 시간초과가 일어났다. 최악의 경우 2의 30승만큼 반복하니 그럴법도 했다.

시간을 줄이기 위해, 행렬을 4분할한뒤 (r,c)가 어느 사분면에 속하는지 확인하고, 속하지 않는 이전 사분면의 수만큼 카운트를 더해준 뒤 위치하는 사분면에 대해서 분할하는 방식으로 접근해보게 됐다.
행렬의 크기를 재정의 하거나, 행렬을 4분할 할 때 분할되는 곳의 좌표를 파악하는 것이 중요했다.

코드

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

public class Main {
	static int count = 0;
	static int n, a, b;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str = bf.readLine();
		StringTokenizer st = new StringTokenizer(str);
		
		n = Integer.parseInt(st.nextToken());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		culc(n, 0, (int)Math.pow(2, n), 0, (int)Math.pow(2, n));
		System.out.println(count-1);
	}

	private static void culc(int now, int x1, int x2, int y1, int y2) {
			while(now != 1) {
				int length = (x2-x1)/2;
				int halfx = x2 - ((x2-x1)/2);
				int halfy = y2 - ((y2-y1)/2);
				if(a >= x1 && a < halfx && b >= y1 && b < halfy) {
					x2 = halfx;
					y2 = halfy;
				}
				else if(a >= x1 && a < halfx && b >= halfy && b < y2) {
					count += length * length;
					x2 = halfx;
					y1 = halfy;
				}
				else if(a >= halfx && a < x2 && b >= y1 && b < halfy) {
					count += length * length * 2;
					x1 = halfx;
					y2 = halfy;
				}
				else if(a >= halfx && a < x2 && b >= halfy && b < y2) {
					count += length * length * 3;
					x1 = halfx;
					y1 = halfy;
				}
				now--;
			}
			
			if(a == x1) {
				if(b == y1)
					count++;
				else
					count+=2;
			}
			else {
				if(b == y1)
					count+=3;
				else
					count+=4;
			}
	}
}

추가

n, r, c = map(int, input().split())
result = 0
k = pow(2, n)
while k>1:
    k = k//2
    if c >= k:
        result += k*k
        c-=k
    if r >= k:
        result += 2*k*k
        r-=k
print(result)

친구가 작성한 코드를 추가로 올린다.
행렬을 4분할 하고 (r,c)가 위치하는 사분면에 따라 행렬의 위치와 크기를 재정의하는 방식이 아니라, (r,c)의 위치를 변화시켜 훨씬 깔끔하고 알기쉬운 코드가 되었다.