문제

풀이

Z 모양의 가장 큰 특징은 하나의 그림이 사각형을 이루고 연속된 수가 모여 있는 점이다.

4x4의 행렬이 있을 때 Z를 이루는 작은 사각형을 각각 사분면으로 구분하자. 예를 들어, 1사분면은 0~3을 나타내고, 2사분면은 4~7을 나타내게 된다. 그렇다면 그보다 작은 2x2 행렬은 어떻게 될까? 2x2 행렬 역시 똑같이 사분면으로 구분가능하다.

따라서, 전체 행렬로부터 우리가 찾아야 하는 위치를 사분면으로 표현할 수 있다. 예를 들어, 위와 같은 4x4 행렬에서 (3,2)은 사분면 표현으로 3 -> 1로 나타낼 수 있다.

그렇다면 해당 행렬 위치의 값은 어떻게 구할 수 있을까? 우선 행렬에 따라서 범위를 제한해야 한다. 2x2에서 3사분면이라면 범위는 8~11이 된다. 그 다음으로 1사분면이라면 8을 나타내기 때문에 3 -> 1 위치의 값은 8이 된다.

코드

package java_baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class prob1074 {
    static int N;
    static int r;
    static int c;
    static Queue<Integer> que;

    public static void main(String[] args) throws IOException {
        que = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s1[] = br.readLine().split(" ");

        N = Integer.parseInt(s1[0]);
        r = Integer.parseInt(s1[1]);
        c = Integer.parseInt(s1[2]);

        int index_row[] = { 0, (int) Math.pow(2, N) - 1 };
        int index_col[] = { 0, (int) Math.pow(2, N) - 1 };

        int min = 0;
        int max = (int) Math.pow(Math.pow(2, N), 2) - 1;

        while (true) { // 4분면 탐색 과정
            int row_bound = index_row[0] + (index_row[1] - index_row[0]) / 2;
            int col_bound = index_col[0] + (index_col[1] - index_col[0]) / 2;
            int quadrant = 0;

            if (r >= index_row[0] && r <= row_bound && c >= index_col[0] && c <= col_bound) {       //1사분면
                index_row[1] = row_bound;
                index_col[1] = col_bound;
                quadrant = 1;
            } else if (r >= index_row[0] && r <= row_bound && c > col_bound && c <= index_col[1]) { //2사분면
                index_row[1] = row_bound;
                index_col[0] = col_bound + 1;
                quadrant = 2;
            } else if (r > row_bound && r <= index_row[1] && c >= index_col[0] && c <= col_bound) { //3사분면
                index_row[0] = row_bound + 1;
                index_col[1] = col_bound;
                quadrant = 3;
            } else if (r > row_bound && r <= index_row[1] && c > col_bound && c <= index_col[1]) {  //4사분면
                index_row[0] = row_bound + 1;
                index_col[0] = col_bound + 1;
                quadrant = 4;
            } else {
                return;
            }
            que.add(quadrant);
            if (index_row[1] == index_row[0] && index_col[1] == index_col[0]) {        //사분면 특정이 불가능하면 종료
                break;
            }
        }
        while (!que.isEmpty()) {                    //큐에서 사분면 값을 하나씩 꺼내서 범위를 탐색
            int quadrant = que.poll();

            int range = (max - min + 1) / 4;

            min = min + (range * (quadrant - 1));
            max = min + range - 1;

            if(min == max){                         //사분면이 범위가 아닌 특정 값을 가리킬때 종료
                System.out.println(min);
                break;
            }
        }

    }
}

결과