1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서
www.acmicpc.net
분할정복으로 해결할 수 있는 문제입니다.
배열을 같은크기로 4등분하여 나눈 구간을 이런식으로 탐색하는데 r행 c열을 방문하는 순서를 출력해야합니다.
저는 4개의 구간을 인덱스를 이용하여
1구간은 (sx, sy) ~ ((sx + ex) / 2, (sy + ey) / 2)
2구간은 (sx, (sy + ey) / 2 + 1) ~ ((sx + ex) / 2, ey)
3구간은 ((sx + ex) / 2 + 1, sy) ~ (ex, (sy + ey) / 2)
4구간은 ((sx + ex) / 2 + 1, (sy + ey) / 2 + 1) ~ (ex, ey)
이렇게 나눴습니다.
여기서 나눈 좌표들을 (r, c)와 순서대로 비교하여 각 구간에 포함되어있는지 확인합니다.
1구간에 포함되어있으면 1구간을 탐색
2구간에 포함되어있으면 1구간의 크기만큼 ans에 더해주고 2구간을 탐색
3구간에 포함되어있으면 1, 2구간의 크기만큼 ans에 더해주고 3구간을 탐색
4구간에 포함되어있으면 1, 2, 3구간의 크기만큼 ans에 더해주고 4구간을 탐색합니다.
재귀를 돌리다가 size가 1이되면 해당칸에 도착했다는 뜻이니 ans++후에 리턴합니다.
문제에서 순서는 0부터 시작하니 출력은 ans - 1로 해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static boolean chk;
static int N, r, c, ans;
static void func(int size, int sx, int sy, int ex, int ey) {
if (size == 1) {
ans++;
return;
}
if (r <= (sx + ex) / 2 && c <= (sy + ey) / 2)
func(size / 2, sx, sy, (sx + ex) / 2, (sy + ey) / 2);
else if (r <= (sx + ex) / 2 && c > (sy + ey) / 2) {
ans += (size / 2 * size / 2);
func(size / 2, sx, (sy + ey) / 2 + 1, (sx + ex) / 2, ey);
} else if (r > (sx + ex) / 2 && c <= (sy + ey) / 2) {
ans += (size / 2 * size / 2 * 2);
func(size / 2, (sx + ex) / 2 + 1, sy, ex, (sy + ey) / 2);
} else {
ans += (size / 2 * size / 2 * 3);
func(size / 2, (sx + ex) / 2 + 1, (sy + ey) / 2 + 1, ex, ey);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
int size = (1 << N);
func(size, 0, 0, size - 1, size - 1);
System.out.println(ans - 1);
}
}
|
cs |
'algorithm > Divide-and-Conquer' 카테고리의 다른 글
| boj 1992 쿼드트리 (0) | 2021.02.17 |
|---|