1074번 Z

Drumj·2025년 5월 14일

골드5 - 분할 정복, 재귀

소스 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int answer;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            find((int) Math.pow(2, N), r, c);

            bw.write(answer + "\n");
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static void find(int size, int r, int c) {
        if(size == 1)
            return;

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

풀이 방법

우선 찾고자하는 좌표 (r,c)의 위치가 어디에 있는지를 파악해야한다.

주어진 2차원 배열을 4등분 해서 찾는다고 하는데 이걸 사분면으로 나눠서 생각을 하게 되면 왼쪽 위 부터 순서대로 1,2,3,4 사분면이 되는데...

~~(이걸 언제 배웠었더라 사분면...)~~

r과 c가 1사분면에 속한다면, 앞에서 아무데도 방문하지 않았으므로 count를 그냥 두고, find메소드에 현재 size의 절반, 1사분면에서의 r,c 상대위치 r,c를 넘겨준다.

r과 c가 2사분면에 속한다면, 앞에서 1사분면을 방문해야하므로 count에 (size*size)/4를 더한다.
(한 사분면의 크기: 전체 배열 크기의 4등분)
find메소드에 현재 size의 절반, 2사분면에서의 r,c 상대위치 r, c-size/2를 넘겨준다.

r과 c가 3사분면에 속한다면, 앞에서 1,2 사분면을 방문해야하므로 count에 (sizesize)/4 2를 더한다.
find메소드에 현재 size의 절반, 3사분면에서의 r,c 상대위치 r-size/2, c를 넘겨준다.

r과 c가 4사분면에 속한다면, 앞에서 1,2,3 사분면을 방문해야하므로 count에 (sizesize)/4 3를 더한다.
find메소드에 현재 size의 절반, 4사분면에서의 r,c 상대위치 r-size/2, c-size/2를 넘겨준다.

위를 반복하다가 size가 1이 되면 재귀를 끝낸다.

지혜로운 개발로그님의 블로그에서 본 해설이다.

각 사분면의 위치에서 다시 또 4등분을 해서 좌표의 값을 찾아야 하기 때문에 이렇게 문제를 푸는 것.

글을 읽으면 읽을 수록 좀 헷갈리긴 한다 ㅋㅋㅋ... ㅎㅎ;;;

계속해서 4등분을 해서 값을 찾는 과정이라는 것을 이해하자!!

나의 노가다 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            int mapSize = (int) Math.pow(2, N);
            int[][] maps = new int[mapSize][mapSize];

            fillMaps(maps, N, 0 , 0);

            bw.write(maps[r][c] + "\n");
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    static int mapValue = 0;
    private static void fillMaps(int[][] maps, int N, int x, int y) {
        if (N == 0) return;

        //2차원 배열을 2^(N-1) x 2^(N-1)로 4등분 한 후 방문
        int size = (int) Math.pow(2, N - 1);
        if (N == 1) {
            maps[x][y] = mapValue++;
            maps[x][y + 1] = mapValue++;
            maps[x + 1][y] = mapValue++;
            maps[x + 1][y + 1] = mapValue++;
        }

        // 좌표가 (0,0) -> (0,2^(N-1)) -> (2^(N-1),0) -> (2^(N-1),2^(N-1)) 순으로 이동
        fillMaps(maps, N - 1, x, y);
        fillMaps(maps, N - 1, x, y + size);
        fillMaps(maps, N - 1, x + size, y);
        fillMaps(maps, N - 1, x + size, y + size);
    }
}