[백준][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열을 몇 번째로 방문했는지 출력한다.

 

 

 

 

---

 

 

 

/* 풀이방법 */

 

분할 정복방식으로 풀었다. Z모양 배열을 보면 아래와 같은 모양이 반복됨을 알 수 있다.

따라서 3행 1열에 있는 숫자를 구하고 싶다면,

처음 사이즈에서 3사분면 내의 4 사분면에 위치하고 있는 것이다.

따라서 while문안에 size를 나누기2 해가면서 탐색을 해갔다.

 

(+)

1사분면의 첫번째 값 = num의 변화 없음

2사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 2

3사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 3

4사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 4

 

 

 

---

 

/* 해답코드 */

package baekjoon;

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

public class b1074 {

	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());
		
		
		int size = (int)Math.pow(2, N);
		int cr = 0;
		int cc = 0;
		int num  =0;
		while(true) {
			if(cr==r&&cc==c) {
				break;
			}
			
			if(r<(size/2+cr)) {
				//2번
				if(c>=(size/2+cc)){
					num += Math.pow(size/2, 2);
					cc+=size/2;
				}
			}else {
				//3번
				if(c<(size/2+cc)) {
					num += Math.pow(size/2, 2)*2;
					cr+=size/2;
				}
				//4번
				else {
					num += Math.pow(size/2, 2)*3;
					cr+=size/2;
					cc+=size/2;
				}
			}			
			size = size/2;
		}
		
		System.out.println(num);
		
	}

}