백준 1074번 Z: 목표가 있는 사분면만 내려가기
모든 칸을 하나씩 세면 어떨까요?
Z 순서대로 모든 칸을 세면 탐색량이 너무 커져 시간 초과가 납니다. 그래서 범위를 나눠 목표가 있는 부분만 계산했습니다.
한 변의 길이가 n인 영역을 네 부분으로 나눕니다. 방문 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래입니다. 목표 좌표 (r, c)가 들어 있는 사분면만 재귀 호출하고 그보다 앞선 사분면의 칸 수는 cnt에 한꺼번에 더합니다.
각 사분면의 한 변은 divN = n / 2이므로 칸 수는 divN * divN입니다. 목표가 두 번째 사분면이면 이 값을 한 번, 세 번째면 두 번, 네 번째면 세 번 더합니다.
아래 코드는 일부 범위 조건의 상한에 현재 영역 크기 n 대신 전체 크기 N을 사용합니다. 그래도 이 코드에서는 다음 사분면을 고를 수 있습니다. 목표가 현재 영역 안에 있다는 전제와 앞선 분기 때문입니다. 다만 현재 영역의 경계를 그대로 표현한 조건은 아닙니다.
영역이 2×2가 되면 네 칸을 순서대로 확인하고 목표 위치의 번호를 출력합니다. 첫 칸의 번호는 0입니다.
당시 제출 코드
import java.io.*;
import java.util.*;
class Main {
static int N, r, c;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = (int) Math.pow(2, Integer.parseInt(st.nextToken()));
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
func(N, 0, 0, 0);
}
static void func(int n, int a, int b, int cnt) throws IOException{
if(n==2){
for (int i = a; i <= a+1; i++) {
for (int j = b; j <= b+1; j++) {
if(i==r && j==c){
bw.write(String.valueOf(cnt));
bw.flush();
return;
}
cnt++;
}
}
} else {
int divN = n / 2;
if ( a <= r &&
r < a + divN &&
b <= c &&
c < b + divN)
func(divN, a, b, cnt);
else if (a <= r &&
r < a + divN &&
b + divN <= c &&
c < b + N)
func(divN, a, b + divN, cnt + divN * divN);
else if (a + divN <= r &&
r < a + N &&
b <= c &&
c < b + divN)
func(divN, a + divN, b, cnt + divN * divN * 2);
else
func(divN, a + divN, b + divN, cnt + divN * divN * 3);
}
}
}