[백준] [Silver I] Z - 1074

[Silver I] Z - 1074

문제 링크

성능 요약

메모리: 14204 KB, 시간: 124 ms

분류

분할 정복, 재귀

제출 일자

2024년 2월 9일 18:28:49

문제 설명

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

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

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

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

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

입력

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

출력

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

코드

 import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int N;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");
            N = Integer.parseInt(split[0]);
            int r = Integer.parseInt(split[1]);
            int c = Integer.parseInt(split[2]);

            int result = 0;

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

            result += divideAndConquer(size, r, c);

            System.out.println(result);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static int divideAndConquer(int size, int r, int c) {
        if (size == 0) {
            return 0;
        }


        int half = size / 2;

        if (r < half && c < half) { // 1사분면
            return divideAndConquer(half, r, c);

        } else if (r < half && half <= c) { // 2사분면
            return (int) Math.pow(half, 2) + divideAndConquer(half, r, c - half);

        } else if (half <= r && c < half) { // 4사분면
            return 2 * ((int) Math.pow(half, 2)) + divideAndConquer(half, r - half, c);

        } else { // 3사분면
            return 3 * ((int) Math.pow(half, 2)) + divideAndConquer(half, r - half, c - half);

        }

    }
}