백준 1074 : Z

1. 문제 : https://www.acmicpc.net/problem/1074

1074번: Z

 

2. 문제 접근

• 완전 탐색
  • 최악의 경우에 $2^{15} X 2^{15} = $약 $10$억 -> Time limit으로 사용 불가능
• 분할 정복
  • $N = K$ 정사각형은 $N = K - 1$ 정사각형 $4$개를 합친 모양 -> 큰 문제를 작은 문제로 분할
  • 모든 노드의 자식 노드가 $4$개인 트리로 전환 가능

 

3. 문제 해결

1. $N = K$ 정사각형을 4개로 분할
2. $N = K - 1$ 정사각형 $4$개 중 $(c, r)$이 어느 영역에 속해있는지 확인
3. $(c, r)$이 속한 정사각형의 모든 노드들은 이전 정사각형까지의 탐색을 모두 마쳐야 함.
4. $N = K - 1$ 정사각형 또한 $N = K - 2$ 정사각형 $4$개를 합친 모양
5. 재귀를 통해 어느 영역에 속해있는지 확인하면 $N = 1$ 정사각형의 좌표가 $(c, r)$

 

4. 코드

#include <iostream>
using namespace std;

// -----------------------------
//		|	
//	1	|	2
//		|
// -----------------------------
//		|
//	3	|	4
//		|
// -----------------------------

int dc(int c, int r, int x, int y, int size)
{
	// if the size is 1, the coordinates are the target (c, r)
	if (size == 1) return 0;

	// Set the size of the square of N = K - 1
	int mid = size / 2;

	// Quadrant 1, 3
	if (c < x + mid)
	{
		// Quadrant 1
		if (r < y + mid) return dc(c, r, x, y, mid);
		// Quadrant 3
		else return mid * mid * 2 + dc(c, r, x, y + mid, mid);
	}
	// Quadrant 2, 4
	else
	{
		// Quadrant 2
		if (r < y + mid) return mid * mid * 1 + dc(c, r, x + mid, y, mid);
		// Quadrant 4
		else return mid * mid * 3 + dc(c, r, x + mid, y + mid, mid);
	}
}

int solution(int N, int r, int c)
{
	int size = 1;

	// Set the initial size
	for (int i = 0; i < N; i++)
	{
		size *= 2;
	}

	return dc(c, r, 0, 0, size);
}

int main()
{
	int N, r, c;
	
	cin >> N >> r >> c;
	
	cout << solution(N, r, c);

	return 0;
}