[백준/Java] Z

🔗 문제 링크:  https://www.acmicpc.net/problem/1074

🔍 해결 과정

보드판을 살펴보는 흐름에서 규칙을 찾아내는 것이 중요합니다. 문제에서 n이 2일 때의 보드판(4 x 4)을 예시로 들 때 Z를 기준으로 4가지의 영역으로 보드판을 나눌 수가 있습니다.

각 영역에 대해서 가지고 있는 좌표를 Z의 흐름대로 살표본다면 다음과 같이 정리할 수가 있습니다.

• 제 1사분면에서 살펴보는 순서: 1번 (0, 0), 2번 (0, 1), 3번 (1, 0), 4번 (1, 1)
• 제 2사분면에서 살펴보는 순서: 5번 (0, 2), 6번 (0, 3), 7번 (1, 2), 8번 (1, 3)
• 제 3사분면에서 살펴보는 순서: 9번 (2, 0), 10번 (2, 1), 11번 (3, 0), 12번 (3, 1)
• 제 4사분면에서 살펴보는 순서: 13번 (2, 2), 14번 (2, 3), 15번 (3, 2), 16번 (3, 3)

보드판의 크기는 2의 제곱승으로 가로와 세로를 나눌 수 있으므로 이를 바탕으로 다음과 같은 공식을 도출할 수가 있습니다.

• 제 1사분면 안에 찾으려는 좌표가 존재하는 경우 해당 좌표의 번호: 0 x (보드판의 절반길이의 제곱) + 해당 사분면에서의 좌표 순번
• 제 2사분면 안에 찾으려는 좌표가 존재하는 경우 해당 좌표의 번호: 1 x (보드판의 절반길이의 제곱) + 해당 사분면에서의 좌표 순번
• 제 3사분면 안에 찾으려는 좌표가 존재하는 경우 해당 좌표의 번호: 2 x (보드판의 절반길이의 제곱) + 해당 사분면에서의 좌표 순번
• 제 4사분면 안에 찾으려는 좌표가 존재하는 경우 해당 좌표의 번호: 3 x (보드판의 절반길이의 제곱) + 해당 사분면에서의 좌표 순번

예를 들어서 위 예시에서 (3, 0)을 살펴본다고 한다면 해당 좌표는 제 3사분면에 위치하므로 다음과 같은 공식으로 좌표 순번을 도출할 수가 있습니다.

2 x (2 x 2) + 3 = 11

 

찾으려는 해당 좌표를 보드판 선분의 절반 길이의 값이랑 비교하여 어떤 영역에 있는지 파악하고 그에 적절하게 공식을 적용하여 재귀호출을 하여 문제를 해결하면 됩니다.

---

✏️ 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        bw.write(Integer.toString(solution(Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()))));
        bw.flush();
        bw.close();
    }

    private static int solution(int n, int r, int c) {
        if (n == 0) {
            return 0;
        }

        int half = 1 << (n - 1);

        if (r < half && c < half) {
            return solution(n - 1, r, c);
        } else if (r < half) {
            return half * half + solution(n - 1, r, c - half);
        } else if (c < half) {
            return 2 * half * half + solution(n - 1, r - half, c);
        } else {
            return 3 * half * half + solution(n - 1, r - half, c - half);
        }
    }
}