백준 1074 Z (Java)

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

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

public class Main {

    static int cnt = 0;

    static int r;
    static int c;


    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine(), " ");

        int n = Integer.parseInt(tokenizer.nextToken());


        //r, c는 0-indexed
        r = Integer.parseInt(tokenizer.nextToken());
        c = Integer.parseInt(tokenizer.nextToken());

        int size = (int) Math.pow(2, n);


        solve(size, r, c);

        System.out.println(cnt);
    }

    private static void solve(int size, int r, int c) {


        if(size == 1)
            return;

        if(r < size/2 && c < size/2) {
            solve(size/2, r, c);
        }
        else if(r < size/2 && c >= size/2) {
            cnt += size * size / 4;
            solve(size/2, r, c - size/2);
        }
        else if(r >= size/2 && c < size/2) {
            cnt += (size * size / 4) * 2;
            solve(size/2, r - size/2, c);
        }
        else {
            cnt += (size * size / 4) * 3;
            solve(size/2, r - size/2, c - size/2);
        }

    }
}

1. 문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

제한

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

2. 풀이

해당 문제를 전수조사로 풀게 되면 시간초과가 발생한다. 따라서 계산으로 접근하여 divide and conquer를 해야 한다.

 

해당 문제는 Z 방향으로 움직인다. 배열 하나가 있으면 해당 배열을 4등분하여 좌상, 우상, 좌하, 우하 순으로 방문하게 된다.

 

r, c에 해당하는 숫자를 찾아야 한다. 각 등분의 가장 작은 숫자를 확인하여 이를 비교한다. 

위의 그림이다. 해당 그림을 4등분하면 0-15, 16-31, 32-47, 48-63이다. 각 등분의 가장 작은 숫자는 0, 16, 32, 48이다.

즉, 전체 숫자의 개수를 4등분하고, 이를 계산해나가면서 r, c에 해당하는 숫자를 찾을 수 있다.

이에 따른 재귀함수는 다음과 같다.

private static void solve(int size, int r, int c) {


        if(size == 1)
            return;

        if(r < size/2 && c < size/2) {
            solve(size/2, r, c);
        }
        else if(r < size/2 && c >= size/2) {
            cnt += size * size / 4;
            solve(size/2, r, c - size/2);
        }
        else if(r >= size/2 && c < size/2) {
            cnt += (size * size / 4) * 2;
            solve(size/2, r - size/2, c);
        }
        else {
            cnt += (size * size / 4) * 3;
            solve(size/2, r - size/2, c - size/2);
        }

    }

r, c열의 숫자를 r, c의 크기에 따라 잘라준다. 예를 들어 위 그림의 2번째는 16부터 시작하여 Z 방문을 하는 4*4 배열이다.