백준 1891 자바 - 사분면

https://www.acmicpc.net/problem/1891

1891번: 사분면

문제

하나의 좌표평면은 다음과 같이 네 개의 사분면으로 나뉜다.

그러면, 각각의 사분면을 다시 사분면으로 나누어 번호를 붙여 보면 어떨까? 예를 들어 1번 사분면의 1번 사분면은 11번 사분면, 3번 사분면의 2번 사분면은 32번 사분면이라고 하면 좋지 않을까? 물론 한 번 더 나눠 볼 수도 있겠다. 3번 사분면의 4번 사분면의 1번 사분면은 341번 사분면이다.

사분면의 번호 길이가 길어짐에 따라 각각의 사분면의 크기는 급격히 작아지며, 그 개수는 기하급수적으로 증가한다.

사분면에 번호를 붙이는 이러한 규칙을 상정하고서, 어떤 사분면 조각을 이동시켰을 때, 그 조각이 위치하게 되는 사분면의 번호가 궁금하다. 예를 들어, 341번 사분면을 오른쪽으로 두 번, 위쪽으로 한 번 이동시키면 424번 사분면에 온다.

하나의 사분면 조각을 이동시켰을 때, 그 조각이 도착한 사분면의 번호를 알아내는 프로그램을 작성하라.

코드

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

public class Main {

    private static int d;
    private static String num;
    private static Element dxdy, nxny;
    private static String answer = "";

    public static void main(String[] args) throws IOException {
        BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        d = Integer.parseInt(st.nextToken());
        num = st.nextToken();
        st = new StringTokenizer(br.readLine());
        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());
        long n = 1L << d, m = n;


        find(0, n, 0, m, 0);
        nxny = new Element((-1 * y) + dxdy.x, x + dxdy.y);

        if (0 <= nxny.x && nxny.x < n && 0 <= nxny.y && nxny.y < m) {
            check(0, n, 0, m);
            bw.write(answer);
        }
        else bw.write("-1");
        bw.flush();

    }

    private static String check(long n1, long n2, long m1, long m2) {
        if (answer.length() == d) return answer;
        if (n1 <= nxny.x && nxny.x < (n1 + n2) / 2 && (m1 + m2) / 2 <= nxny.y && nxny.y < m2) {
            answer += "1";
            return check(n1, (n1 + n2) / 2, (m1 + m2) / 2, m2);
        } else if (n1 <= nxny.x && nxny.x < (n1 + n2) / 2 && m1 <= nxny.y && nxny.y < (m1 + m2) / 2) {
            answer += "2";
            return check(n1, (n1 + n2) / 2, m1, (m1 + m2) / 2);
        } else if ((n1 + n2) / 2 <= nxny.x && nxny.x < n2 && m1 <= nxny.y && nxny.y < (m1+m2) / 2) {
            answer += "3";
            return check((n1 + n2) / 2, n2, m1, (m1 + m2) / 2);
        } else {
            answer += "4";
            return check((n1 + n2) / 2, n2, (m1 + m2) / 2, m2);
        }
    }

    private static void find(long n1, long n2, long m1, long m2, int index) {
        if (index == d) {
            dxdy = new Element(n1, m1);
            return;
        }
        int number = num.charAt(Integer.parseInt(String.valueOf(index))) - '0';

        if (number == 1) find(n1, (n1 + n2) / 2, (m1 + m2) / 2, m2, index + 1);
        else if (number == 2) find(n1, (n1 + n2) / 2, m1, (m1 + m2) / 2, index + 1);
        else if (number == 3) find((n1 + n2) / 2, n2, m1, (m1 + m2) / 2, index + 1);
        else if (number == 4) find((n1 + n2) / 2, n2, (m1 + m2) / 2, m2, index + 1);
    }

    private static class Element {
        long x, y;
        public Element(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
}

풀이

find 함수로 어느 위치일지 찾고, 한 번에 x와 y의 값을 가지는 Element 클래스의 인스턴스 dxdy를 초기화시켜준다. 그 후 check 함수에서 사분면을 4 부분으로 나눠가며 정답을 찾는다. 자바로 풀어서 타입 오류를 조심해야 한다. num 변수는 String으로 하는 편이 좋다.