문제출처: https://www.acmicpc.net/problem/1074
문제 설명
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=2일 때의 예이다.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2N
예제 입력
2 3 1
예제 출력
11
예제 입력
3 7 7
예제 출력
63
예제 입력
10 511 511
예제 출력
262143
문제 풀이
import java.io.*;
import java.util.Arrays;
class Main {
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int N = (int) Math.pow(2, input[0]);
int r = input[1];
int c = input[2];
findOrder(r, c, N * N);
System.out.println(count);
br.close();
}
public static void findOrder(int r, int c, int size) {
if(size == 1) {
return;
} else {
if(r < size / 2 && c < size / 2) {
findOrder(r, c , size / 2);
} else if(r < size / 2 && c >= size / 2) {
count += size * size / 4;
findOrder(r, c - size / 2, size / 2);
} else if(r >= size / 2 && c < size / 2) {
count += size * size / 4 * 2;
findOrder(r - size / 2, c, size / 2);
} else {
count += size * size / 4 * 3;
findOrder(r - size / 2, c - size / 2, size / 2);
}
}
}
}
풀이 방법
위 그림을 참고해서 4분탐색 재귀 호출을 해서 위치에 도달했을때의 숫자를 찾으면 된다.
ex) 3, 7, 7
N = 3
찾아야하는 위치 row 7, col 7
N이 3일때, row와 col의 길이는 각각 8이다. 2^3 X 2^3이다.
첫번째 재귀 호출에서 row 7과 col 7은 size / 2인 둘다 4보다 크므로 count += 48 (size 8 x 8 / 4 x 3)을 하고 row와 col의 값에서 사이즈 8 / 2인 4를 빼고 사이즈 8을 반으로 줄인다.
두번째 재귀 호출 row 3, row 3은 size / 2인 둘다 2보다 크므로 count += 12 (size 4 x 4 / 4 x 3)을 하고 row와 col의 값에서 사이즈 4 / 2인 2를 빼고 사이즈 4를 반으로 줄인다.
세번째 재귀 호출 row 1, row 1은 size / 2인 둘다 1보다 크므로 count += 3 (size 2 x 2 / 4 x 3)을 하고 row와 col의 값에서 사이즈 2 / 2인 1를 빼고 사이즈 2를 반으로 줄인다.
size 가 1이되어서 함수 호출이 종료 된다.
count = 63을 출력한다.
