백준 - Z[java]

문제출처: https://www.acmicpc.net/problem/1074

문제 설명

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

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

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

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

입력

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

출력

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

제한

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

예제 입력

2 3 1

예제 출력

11

예제 입력

3 7 7

예제 출력

63

예제 입력

10 511 511

예제 출력

262143

문제 풀이

import java.io.*;
import java.util.Arrays;

class Main {

    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = (int) Math.pow(2, input[0]);
        int r = input[1];
        int c = input[2];
        findOrder(r, c, N * N);
        System.out.println(count);
        br.close();
    }

    public static void findOrder(int r, int c, int size) {

        if(size == 1) {
            return;
        } else {
            if(r < size / 2 && c < size / 2) {
                findOrder(r, c , size / 2);
            } else if(r < size / 2 && c >= size / 2) {
                count += size * size / 4;
                findOrder(r, c - size / 2, size / 2);
            } else if(r >= size / 2 && c < size / 2) {
                count += size * size / 4 * 2;
                findOrder(r - size / 2, c, size / 2);
            } else {
                count += size * size / 4 * 3;
                findOrder(r - size / 2, c - size / 2, size / 2);
            }
        }
    }
}

풀이 방법

위 그림을 참고해서 4분탐색 재귀 호출을 해서 위치에 도달했을때의 숫자를 찾으면 된다.

ex) 3, 7, 7

N = 3

찾아야하는 위치 row 7, col 7

N이 3일때, row와 col의 길이는 각각 8이다. 2^3 X 2^3이다.

첫번째 재귀 호출에서 row 7과 col 7은 size / 2인 둘다 4보다 크므로 count += 48 (size 8 x 8 / 4 x 3)을 하고 row와 col의 값에서 사이즈 8 / 2인 4를 빼고 사이즈 8을 반으로 줄인다.

두번째 재귀 호출 row 3, row 3은 size / 2인 둘다 2보다 크므로 count += 12 (size 4 x 4 / 4 x 3)을 하고 row와 col의 값에서 사이즈 4 / 2인 2를 빼고 사이즈 4를 반으로 줄인다.

세번째 재귀 호출 row 1, row 1은 size / 2인 둘다 1보다 크므로 count += 3 (size 2 x 2 / 4 x 3)을 하고 row와 col의 값에서 사이즈 2 / 2인 1를 빼고 사이즈 2를 반으로 줄인다.

size 가 1이되어서 함수 호출이 종료 된다.

count = 63을 출력한다.