[백준, BOJ 1074] Z (java)

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

1074번: Z

---

문제

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

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

다음 예는 $2^2 \times 2^2$크기의 배열을 방문한 순서이다.

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

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < $2^N$

728x90

 

예제 입력 1

2 3 1

예제 출력 1

11

 

예제 입력 2

3 7 7

예제 출력 2

63

 

예제 입력 3

1 0 0

예제 출력 3

0

 

예제 입력 4

4 7 7

예제 출력 4

63

 

예제 입력 5

10 511 511

예제 출력 5

262143

 

예제 입력 6

10 512 512

예제 출력 6

786432

---

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

public class Main {
	static int count = 0;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		z((int) Math.pow(2, n), r, c);
		System.out.println(count);
	}
	
	static void z(int size, int x, int y) {
		if (size == 1)
			return;
		// 정사각형을 크게 4등분 했을 때, 왼쪽 위(1사분면), 오른쪽 위(2사분면), 왼쪽 아래(3사분면), 오른쪽 아래(4사분면) 이라고 하자.
		// 1사분면에 위치
		if ((x >= 0) && (x < size / 2) && (y >= 0) && (y < size / 2)) {
			z(size / 2, x, y);
		}
		// 2사분면에 위치
		else if ((x >= 0) && (x < size / 2) && (y >= size / 2) && (y < size)) {
			count += size * size / 4;
			z(size / 2, x, y - size / 2);
		}
		// 3사분면에 위치
		else if ((x >= size / 2) && (x < size) && (y >= 0) && (y < size / 2)) {
			count += size * size / 4 * 2;
			z(size / 2, x - size / 2, y);
		}
		// 4사분면에 위치
		else {
			count += size * size / 4 * 3;
			z(size / 2, x - size / 2, y - size / 2);
		}
	}

}