문제
풀이
평소 dp, 그래프탐색, greedy 위주로 문제를 풀다가 거의 처음 마주한 분할정복 문제였다.
감조차 잡히지 않아서 다른 블로그들을 참고하여 이해했다.
(이 코드에서 사용한 사분면의 순서는 편의상 수학에서 사용하는 사분면의 순서와는 다르게 설정했다. Z 움직임의 순서가 사분면의 번호이다.)
재귀함수에 y,x,size 값이 들어온다. 여기서 y,x는 현재 탐색하고자 하는 사분면의 가장 왼쪽 위 좌표이며, size는 현재 사분면의 크기이다(정확히는 한 변의 길이).
1
2
void Z(int y, int x, int size)
{
찾고자 하는 좌표 값 r,c가 현재 사분면 내에 존재한다면 현재 사분면을 다시 4등분하여, 현재 4분면의 1,2,3,4 분면 각각의 재귀함수를 호출한다.
1
2
3
4
5
6
7
8
9
10
11
if (r < y + size && r >= y && c < x + size && c >= x)
{
// 1사분면 탐색
Z(y, x, size / 2);
// 2사분면 탐색
Z(y, x + size / 2, size / 2);
// 3사분면 탐색
Z(y + size / 2, x, size / 2);
// 4사분면 탐색
Z(y + size / 2, x + size / 2, size / 2);
}
만약 r,c가 현재 사분면 내에 존재하지 않다면 현재 사분면을 탐색할 필요가 없으므로 ans에 현재 사분면의 크기 size^2을 더해준 후 return 해준다.
1
2
3
4
else
{
ans += size * size;
}
그렇게 호출 되면서 y,x값이 r,c값과 일치하면 최종적으로 답을 출력하고 return 해준다.
1
2
3
4
5
if (y == r && x == c)
{
cout << ans << '\n';
return;
}
소스 코드
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
#include <iostream>
using namespace std;
int n, r, c;
int ans;
void Z(int y, int x, int size)
{
if (y == r && x == c)
{
cout << ans << '\n';
return;
}
// r,c가 현재 사분면에 존재한다면
if (r < y + size && r >= y && c < x + size && c >= x)
{
// 1사분면 탐색
Z(y, x, size / 2);
// 2사분면 탐색
Z(y, x + size / 2, size / 2);
// 3사분면 탐색
Z(y + size / 2, x, size / 2);
// 4사분면 탐색
Z(y + size / 2, x + size / 2, size / 2);
}
else
{
ans += size * size;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> r >> c;
Z(0, 0, (1 << n));
return 0;
}
