Problem
Z 모양으로 순회하는 순서를 알아내는 문제입니다.
Solution
처음 보는 순간 재귀가 떠오릅니다.
사각형을 4개의 사분면으로 나누어서 순서대로 들어가고 또 그 사각형 내에서 4등분 하여 접근합니다.
그렇게 사각형을 더이상 나누지 못하는 1이 될 때까지 재귀를 들어간 후에 카운트 해주면 됩니다.
(x, y, size);
(0, 0, 8);
(0, 0, 4);
(0, 0, 2);
(0, 0, 1);
(1, 0, 1);
(0, 1, 1);
(1, 1, 1);
(2, 0, 2);
(0, 2, 2);
(2, 2, 2);
(4, 0, 4);
(4, 0, 2);
(6, 0, 2);
(4, 2, 2);
(6, 2, 2);
(0, 4, 4);
(4, 4, 4);
간단하게 표현한건데 재귀에 들어가는 모습을 시각적으로 표현한 겁니다.
전부 다 나타낸 것은 아니고 일부만 나타낸 거지만 size가 1이 될 때까지 계속해서 사각형을 나누어 접근합니다.
규칙이 머리속에 바로 떠오르지 않는다면 이렇게 간단하게 적어보시면 금방 찾을 수 있습니다.
하지만 N 이 최대 15라서 재귀를 사용하며 시간 초과가 발생합니다.
시간을 줄이기 위해서 일일히 좌표에 접근하지 않고 한번에 가는 방법을 생각해보았습니다.
규칙이 보이시나요?
8 * 8 배열 일 때 각 사분면의 첫번째 값은 0, 16, 32, 48 입니다.
4 * 4 배열 일 때 각 사분면의 첫번째 값은 0, 4, 8, 12 입니다.
2 * 2 배열 일 때 각 사분면의 첫번째 값은 0, 1, 2, 3 입니다.
n * n 배열 일 때 각 사분면의 첫번째 값은
(n/2) * (n/2) * 0
(n/2) * (n/2) * 1
(n/2) * (n/2) * 2
(n/2) * (n/2) * 3
이렇게 됩니다.
count 에 대한 식을 이렇게 얻었습니다.
Exmaple
n 이 8 인 경우 (2, 3) 좌표를 찾아가보겠습니다.
Step 1. n = 8
먼저 (2, 3) 좌표는 (n / 2, n / 2) 인 (4, 4) 좌표보다 x, y 좌표가 둘다 작습니다.
그래서 왼쪽 위 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.
Step 2. n =4
그리고 다시 (2, 3) 좌표는 (n / 2, n / 2) 인 (2, 2) 좌표보다 x, y 좌표가 둘다 크거나 같습니다.
그래서 오른쪽 아래 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.
Step 3. n = 2
오른쪽 아래 사각형은 (2, 2) 좌표가 첫번째 값입니다.
그러므로 (2 + n / 2, 2 + n / 2) 인 (3, 3) 좌표와 값을 비교합니다.
(2, 3) 좌표는 (3, 3) 좌표보다 x 좌표는 작지만 y 좌표는 크거나 같기 때문에 오른쪽 위 사각형으로 이동합니다.
그리고 n 을 절반으로 하면 1 이 되기 때문에 더 이상 나눌 수 없고 해당 좌표의 카운트를 출력합니다.
말로 설명하기 어려운 부분이 있는데 그림을 보며 코드를 따라가시면 금방 이해할 수 있습니다.
Java Code
import java.util.*;
import java.io.*;
class Main {
static int stoi(String s) { return Integer.parseInt(s);}
static int N;
static int r;
static int c;
static int count = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = stoi(st.nextToken());
int r = stoi(st.nextToken());
int c = stoi(st.nextToken());
int n = getSize(N);
int count = 0;
int x = 0;
int y = 0;
/**
* 사각형 절반으로 나눠서 각 사분면으로 계산
* n 이 1 이 된다는 것은 x, y 좌표가 r, c랑 같아진다는 것
*/
while (n > 0) {
n /= 2;
// 2사분면 (왼 위)
if (r < x+n && c < y+n) {
count += n * n * 0;
}
// 1사분면 (오른 위)
else if (r < x+n) {
count += n * n * 1;
y += n;
}
// 3사분면 (왼 아래)
else if (c < y+n) {
count += n * n * 2;
x += n;
}
// 4사분면 (오른 아래)
else {
count += n * n * 3;
x += n;
y += n;
}
if(n == 1) {
System.out.println(count);
break;
}
}
}
static int getSize(int n) {
int result = 1;
for(int i=0; i<n; i++) {
result *= 2;
}
return result;
}
}