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가 주어진다.

입출력 예

2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

아이디어

분할 정복 대표적인 느낌인데 시간 0.5초밖에 안 줌 ㅁㅊ음?

제출 코드

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

// https://www.acmicpc.net/problem/1074
public class one1074 {
    static int row;
    static int col;

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int n = (int) Math.pow(2, Integer.parseInt(infoToken.nextToken()));
        row = Integer.parseInt(infoToken.nextToken());
        col = Integer.parseInt(infoToken.nextToken());
        int count = -1;
        zsearch(0, 0, n, count);
    }

    public int zsearch(int startRow, int startCol, int n, int count) {
        if (n != 2) {
            int divide = n / 2;
            int n1 = zsearch(startRow, startCol, divide, count);
            int n2 = zsearch(startRow, startCol+ divide, divide, n1);
            int n3 = zsearch(startRow + divide, startCol, divide, n2);
            int n4 = zsearch(startRow + divide, startCol + divide, divide, n3);
            return n4;
        } else {
            int[] drow = new int[]{0, 0, 1, 1};
            int[] dcol = new int[]{0, 1, 0, 1};
            for (int i = 0; i < 4; i++) {
                int nrow = startRow + drow[i];
                int ncol = startCol + dcol[i];
                count++;
                if (nrow == row && ncol == col) {
                    System.out.println(count);
                    System.exit(0);
                    return count;
                }
            }
            return count;
        }
    }

    public static void main(String[] args) throws IOException {
        new one1074().solution();
    }
}

역시나 시간 초과 → 검사하지 말고 사분면으로 나눠서 거기에 해당 안 되면 패스하면 됨

재제출

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

// https://www.acmicpc.net/problem/1074
public class one1074 {
    static int row;
    static int col;

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int n = (int) Math.pow(2, Integer.parseInt(infoToken.nextToken()));
        row = Integer.parseInt(infoToken.nextToken());
        col = Integer.parseInt(infoToken.nextToken());
        int count = 0;
        int nRow = 0;
        int nCol = 0;
        while(n > 0) {
            n /= 2;
            if (row < nRow + n && col < nCol + n) count += 0;
            else if (row < nRow + n) {
                nCol += n;
                count += n * n;
            }
            else if (col < nCol + n) {
                nRow += n;
                count += 2 * n * n;
            }
            else {
                nRow += n;
                nCol += n;
                count += 3 * n * n;
            }
            if (n == 1) {
                System.out.println(count);
                break;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        new one1074().solution();
    }
}