문제
풀이
문제에서 제시한 조각 번호를 통해 사분면에서 해당 조각번호가 어느 위치에 존재하는지 먼저 찾는다.
찾은 위치 (find_x, find_y) 와 입력으로 주어진 x값과 y값을 이용해 찾고자하는 조각 번호를 알아낼 수 있다.
조각번호가 어느 위치에 존재하는지 찾기
구현한 함수를 먼저 알아보자
public static void findLoc(int index, long lx, long ly, long rx, long ry) {
if(index == d) {
find_x = lx;
find_y = ly;
return;
}
int num = findNum_s.charAt(index) - '0';
if(num == 1) {
findLoc(index+1,lx,(ly+ ry)/2,(lx + rx) /2, ry);
}
else if(num == 2) {
findLoc(index+1,lx,ly,(lx + rx)/2 , (ly + ry) / 2);
}
else if(num == 3) {
findLoc(index+1,(lx+rx)/2,ly,rx , (ly + ry) / 2);
}
else if(num == 4) {
findLoc(index+1,(lx+rx)/2,(ly + ry) / 2, rx , ry);
}
} 일단 findeLoc이라는 함수는 인자로 다음과 같은 값들을 받는다
index
조각 번호의 index에 해당하는 num을 찾는 용도이다.
lx
찾을려는 종이 조각의 row위치를 뜻한다.
ly
찾을려는 종이 조각의 colum위치를 뜻한다.
rx
찾을려는 종이 조각이 현재 위치하는 사분면의 마지막 row값 + 1인 값이다.
ry
찾을려는 종이 조각이 현재 위치하는 사분면의 마지막 col값 + 1인 값이다.
해당 함수는 다음과 같이 호출된다.
long n = 1L << d;
findLoc(0, 0, 0, n, n);조각 번호가 1자리라면 사분면의 한 변의 길이는 2가된다.
조각 번호가 2자리라면 사분면의 한 변의 길이는 2*2가 된다.
즉 조각 번호의 자릿수가 d일때 종이조각의 한 변의 길이는
1 << d와 같다.
d가 3이고 찾을려는 종이 조각이 341이라고 한다면 다음과 같이 호출 될 것이다.
1. findLoc(0, 0, 0, 8, 8)
2. findLoc(1, 4, 0, 8, 4) (3사분면)
3. findLoc(2, 6, 2, 8, 4) (3사분면에서의 4사분면)
4. findLoc(3, 6, 3, 7, 4) (3사분면에서의 4사분면에서의 1사분면)
index == d 이므로 return
찾고자 하는 조각 번호 알아내기
먼저 찾은 종이조각의 위치를 통해 입력으로 주어진 x와 y값을 더해준다.
이때 입력으로 주어지는 x의 값은 colum값이고 y값은 row값이다. 그래서 순서를 바꿔 입력을 받았다.
y = Long.parseLong(st.nextToken());
x = Long.parseLong(st.nextToken());
find_x -= x;
find_y += y;그럼 이제 위치를 구했겠다 조각 번호를 알아내보자.
찾을려는 조각 번호의 자릿수가 4고 조각 위치는 (5,5)라고 해보자
어떻게 하면 찾을 수 있을까??
먼저 사분면의 한변의 길이를 구해야한다.
사분면의 한변의 길이는 다음과 같이 구할 수 있다.
long size = 1L << (length - 1);length라는 변수를 둔 이유는 다음과 같다.
424라는 값이 있을때
처음 사분면은 4이고 해당 사분면의 한변의 길이는 4이다.
다음 사분면은 2이고 해당 사분면의 한변의 길이는 2이다.
다음 사분면은 1이고 해당 사분면의 한변의 길이는 1이다.
즉 종이 조각의 번호에 인덱스가 증가할 수 록 사분면의 한변의 길이는 감소한다.
사분면의 한변의 길이를 알아냈다면 이 길이와 사분면에서의 row,colum값을 이용해 다음 사분면이 뭔지 알 수 있다.
이를 통해 함수를 구성하면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static String findNum_s;
static int d;
static long x,y;
static long find_x = 0;
static long find_y = 0;
static long tx,ty;
static StringBuffer sb = new StringBuffer();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
d = Integer.parseInt(st.nextToken());
findNum_s = st.nextToken();
st = new StringTokenizer(br.readLine());
y = Long.parseLong(st.nextToken());
x = Long.parseLong(st.nextToken());
long n = 1L << d;
findLoc(0, 0, 0, n, n);
find_x -= x;
find_y += y;
if(0 <= find_x && find_x < n && 0 <= find_y && find_y < n) {
check(d, find_x, find_y);
System.out.println(sb);
}else {
System.out.println(-1);
}
}
public static void check(int length, long tx, long ty) {
if(length == 0) {
return;
}
long half = 1L << (length - 1);
if(tx < half && ty >= half) {
sb.append("1");
check(length-1, tx, ty-half);
}
else if(tx < half && ty < half) {
sb.append("2");
check(length-1, tx, ty);
}
else if(tx >= half && ty < half) {
sb.append("3");
check(length-1, tx-half, ty);
}
else if(tx >= half && ty >= half) {
sb.append("4");
check(length-1, tx-half, ty-half);
}
}
public static void findLoc(int index, long lx, long ly, long rx, long ry) {
if(index == d) {
find_x = lx;
find_y = ly;
return;
}
int num = findNum_s.charAt(index) - '0';
if(num == 1) {
findLoc(index+1,lx,(ly+ ry)/2,(lx + rx) /2, ry);
}
else if(num == 2) {
findLoc(index+1,lx,ly,(lx + rx)/2 , (ly + ry) / 2);
}
else if(num == 3) {
findLoc(index+1,(lx+rx)/2,ly,rx , (ly + ry) / 2);
}
else if(num == 4) {
findLoc(index+1,(lx+rx)/2,(ly + ry) / 2, rx , ry);
}
}
}
