백준 1891: 사분면 - 분할정복 (파이썬, 자바)

사분면 성공

1891번: 사분면

문제

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

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

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

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

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

 

입력

첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1 ≤ d ≤ 50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y| ≤ 250) 오른쪽으로 이동한 경우 x가 양수, 왼쪽으로 이동한 경우 음수이며, 그 절댓값은 오른쪽 왼쪽 방향 이동 횟수를 나타낸다. 위쪽으로 이동한 경우 y가 양수, 아래쪽으로 이동한 경우 음수이며, 역시 그 절댓값은 아래위 방향 이동 횟수를 나타낸다.

출력

첫 줄에 도착한 사분면의 번호를 출력한다. 만약, 존재하지 않는 사분면인 경우에는 -1을 출력한다.

 

 내 코드

import sys

d,num=sys.stdin.readline().rstrip().split()
d=int(d)
num=list(num)
a,b=map(int,sys.stdin.readline().split())

x,y=0,0 #초기 좌표

n=d #d가 변형되지 않게 n으로 사용.
for i in num:
    i=int(i)
    n-=1 #사이즈를 줄여나감
    size=2**n # =변의 길이

    if i==1: #1사분면
        y+=size
    elif i==2: #2사분면
        pass
    elif i==3: #3사분면
        x+=size
    elif i==4: #4사분면
        x+=size
        y+=size


#좌표를 이동
x-=b
y+=a

answer="" #정답 문자열
for i in range(d):
    limit=2**(d-i) #변의 길이
    half=2**(d-i-1) #변의 길이의 반

    if 0<=x<half and 0<=y<half: #2사분면
        answer+="2"
    elif 0<=x<half and half<=y<limit: #1사분면
        y-=half
        answer+="1"
    elif half<=x<limit and 0<=y<half: #3사분면
        x-=half
        answer+="3"
    elif half<=x<limit and half<=y<limit: #4사분면
        x-=half
        y-=half
        answer+="4"


#유효한 답일 경우만 출력.
if len(answer)==d:
    print(answer)
else:
    print(-1)

 

풀이 및 접근)

- 특정 좌표의 이동 후 좌표를 묻고있으므로, 우선 특정 좌표를 (x,y)화 시켜야 된다고 생각했다.

- 정사각형의 크기만 달라질 뿐, 1, 2, 3, 4사분면의 위치는 어느 정사각형이든 같다.

- 특정 정사각형의 제일 왼쪽위 꼭짓점을 (0,0)이라고 할 때, 2사분면은 (0,0)부터, 1사분면은 (0,변의 길이의 반)부터, 3사분면은 (변의 길이의 반, 0)부터, 4사분면은 (변의 길의의 반, 변의 길의의 반)부터 시작된다. 이 점을 활용하여 초기의 위치가 특정 크기의 정사각형의 어느 사분면에 속하는지를 파악하여 좌표를 계산할 수 있다.

- 계산한 좌표를 바탕으로 좌표를 이동한다. 그리고나서 가장 큰 정사각형일 때부터, 해당 좌표가 어느 사분면에 속하는지를 계속해서 추적하여 출력하면 된다. 문제에서 주어진 정사각형일 때까지 다 쪼개지면, stop하면 된다.

- 정답 문자열의 길이가 문제에서 주어진 d와 같아야 한다. 그렇지 않으면 좌표를 추적하는데 있어서 오류가 났다는 것이다.

 

 

자바 ver.

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

public class BOJ1891 {
    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        int d=Integer.parseInt(st.nextToken());

        String s = st.nextToken();

        char[] num=new char[d];
        for(int i=0; i<d; i++){
            num[i]=s.charAt(i);
        }

        st=new StringTokenizer(br.readLine());
        long a=Long.parseLong(st.nextToken());
        long b=Long.parseLong(st.nextToken());

        long x=0, y=0;

        long n=d;
        for (char i : num) {
            n--;
            long size=(long)Math.pow(2,n);

            if(i=='1'){
                y+=size;
            }
            else if(i=='2'){
                //none
            }
            else if(i=='3'){
                x+=size;
            }
            else if(i=='4'){
                x+=size;
                y+=size;
            }
        }

        x-=b;
        y+=a;

        String answer="";

        for(int i=0; i<d; i++){
            long limit=(long)Math.pow(2,d-i);
            long half=(long)Math.pow(2,d-i-1);

            if(0<=x && x<half && 0<=y && y<half){
                answer+="2";
            }
            else if(0<=x && x<half && half<=y && y<limit){
                y-=half;
                answer+="1";
            }
            else if(half<=x && x<limit && 0<=y && y<half){
                x-=half;
                answer+="3";
            }
            else if(half<=x && x<limit && half<=y && y<limit){
                x-=half;
                y-=half;
                answer+="4";
            }

        }

        if(answer.length()==d){
            System.out.println(answer);
        }
        else{
            System.out.println(-1);
        }
    }
}