[백준 | Java] 1074번 Z - 분할 정복, 재귀

1074번 / Z

❓ Z

🏷️ 관련 주제 : 분할 정복 재귀

---

💦 나의 시도

1. 행,열의 위치 이동 규칙을 찾기

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[][] z = new int[2][2];
        z[0] = new int[]{0, 1};
        z[1] = new int[]{2, 3};

        System.out.println(nextZ(z, r, c));

    }

    public static int nextZ(int[][] preZ, int r, int c) {
        int len = preZ.length;
        int nextLen = len * 2;
        int term = len * len;

        if (r < len && c < len) {
            return preZ[r][c];
        }

        int[][] nextZ = new int[nextLen][nextLen];

        for (int row = 0; row < nextLen; row++) {
            for (int col = 0; col < nextLen; col++) {
                if (row < len) {
                    if (col < len) {
                        nextZ[row][col] = preZ[row][col];
                        continue;
                    }

                    nextZ[row][col] = preZ[row][col - len] + term;
                    continue;
                }

                if (col < len) {
                    nextZ[row][col] = preZ[row - len][col] + term * 2;
                    continue;
                }

                nextZ[row][col] = preZ[row - len][col - len] + term * 3;
                continue;
            }
        }

        return nextZ(nextZ, r, c);
    }
}

---

💽 메모리 초과

제대로된 규칙을 찾으려고 여러차례 시도했으나 실패😣

---

2. 2의 거듭제곱 꼴 정사각형으로 점점 작게 쪼개기

성공🎉

---

📑제출 기록 및 오답 원인

---

💯 해결 방법

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 len = (int) Math.pow(2, N);
        System.out.println(getOrder(r, c, len, 0));

    }

    public static int getOrder(int r, int c, int len, int lt) {
        if (len == 1) {
            return lt;
        }

        int preLen = len / 2;
        int term = preLen * preLen;

        if (r < preLen) {
            if (c < preLen) {
                return getOrder(r, c, preLen, lt);
            }

            return getOrder(r, c - preLen, preLen, lt + term);
        }
        if (c < preLen) {
            return getOrder(r - preLen, c, preLen, lt + term * 2);
        }

        return getOrder(r - preLen, c - preLen, preLen, lt + term * 3);
    }
}