[백준] 1074 - Z | Java

짱챌·2025년 6월 15일

백준 분할정복

Algorithm

목록 보기

14/19

📌 문제 정보

[1074: Z]

💡 접근 방식

일단 헷갈리니까 좌표를 1부터 시작하게 했다.

좌표 범위를 4등분하면서, 찾고자 하는 위치가 어디에 있는지를 찾아야 한다.

1번이면 카운트를 유지하고
2번이면 1번 칸 수만큼 더한다.
3번이면 1번 + 2번 칸 수만큼 더하고
4번이면 1번 + 2번 + 3번 칸 수만큼 더한다.

재귀할 때마다 depth를 증가시키고, 해당하는 위치에 따라 r과 c 값도 변경해주었다.

이걸 반복하면 된다..

✅ 코드

import java.util.*;

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

public class Main {
    static int n, cnt;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        cnt = 0;

        int r = Integer.parseInt(st.nextToken()) + 1;
        int c = Integer.parseInt(st.nextToken()) + 1;

        z(r,c,0);

        System.out.println(cnt);
    }

    private static void z(int r, int c, int depth) {
        int half = n-1-depth;

        if (1 <= r && r <= Math.pow(2, half) ) {
            if (1 <= c && c <= Math.pow(2, half) ) { // 1번


            } else { // 2번
                cnt += (int) Math.pow(4, half);

                c -= (int) Math.pow(2, half);

            }
        } else {
            if (1 <= c && c <= Math.pow(2, half) ) { // 3번
                cnt += (int) Math.pow(4, half) * 2;

                r -= (int) Math.pow(2, half);

            } else { // 4번
                cnt += (int) Math.pow(4, half) * 3;

                r -= (int) Math.pow(2, half);
                c -= (int) Math.pow(2, half);
            }
        }

        if (half == 0) {
            return;
        }

        z(r,c,depth+1);
    }

}