BOJ/1074

Z

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <algorithm>

int main() {

	int n, r, k;
	scanf("%d %d %d", &n, &r, &k);

	r++; k++; // 좌표 계산 편하게 하려고 변경

	int count = 0;

	int aa = 1, bb = 1; // 탐색할 좌표 공간의 왼쪽 위와 오른쪽 아래.
	int cc = (int)pow(2, n);
	int dd = (int)pow(2, n);
	

	while (1) {
		int sa = 0;

		//사분면 판단
		if (r >= aa && r <= cc - (int)pow(2, n - 1) && k >= bb && k <= dd - (int)pow(2, n - 1)) {
			sa = 1;
		}
		else if (r >= aa && r <= cc - (int)pow(2, n - 1) && k <= dd && k > dd - (int)pow(2, n - 1)) {
			sa = 2;
		}
		else if (r <= cc && r > cc - (int)pow(2, n - 1) && k >= bb && k <= dd - (int)pow(2, n - 1)) {
			sa = 3;
		}
		else if (r <= cc && r > cc - (int)pow(2, n - 1) && k <= dd && k > dd - (int)pow(2, n - 1)) {
			sa = 4;
		}
		//next area
		n--;

		if (sa == 1) {
			aa = aa; bb = bb;
			cc -= (int)pow(2, n);
			dd -= (int)pow(2, n);
		}
		else if (sa == 2) {
			bb += (int)pow(2, n);
			aa = aa;
			cc -= (int)pow(2, n);
			dd = dd;
		}
		else if (sa == 3) {
			aa += (int)pow(2, n);
			bb = bb;
			cc = cc;
			dd -= (int)pow(2, n);
		}
		else if (sa == 4) {
			aa += (int)pow(2, n);
			bb += (int)pow(2, n);
			cc = cc;
			dd = dd;
		}

		//순서 구하기
		int size = (int)pow(2, n) * (int)pow(2, n);
		if (sa == 1) {

		}
		else if (sa == 2) {
			count += size * 1;
		}
		else if (sa == 3) {
			count += size * 2;
		}
		else if (sa == 4) {
			count += size * 3;
		}

		if (n == 0) { // 탈출조건
			break;
		}
	}
	

	printf("%d", count);
	
	return 0;
}​

분할정복을 통해 푸는 문제이다. 

처음엔 분할정복이라는 개념을 알지 못해 접근이 힘들었지만 다른 글들을 참고해 좌표가 어떤 사분면에 위치하는지를 판단하여 생각하면 쉬운것을 알게 되었다.

aa,bb / cc,dd를 탐색할 정사각형의 왼쪽 위, 오른쪽 아래 좌표로 두고 해당 범위 내에서 내가 원하는 수가 어떤 위치에 있는지 판단. 해당 사분면의 정사각형의 aa,bb,cc,dd를 새로 설정한 후 다시 사분면 탐색..을 반복하여 원하는 위치를 찾아가는 원리이다.

aa/bb	1	1	1	2	2	2	2
1	1	1	1	2	2	2	2
1	1	1	1	2	2	2	2
1	1	1	1	2	2	2	2
3	3	3	3	4	4	4	4
3	3	3	3	4	4	4	4
3	3	3	3	4	4	4	4
3	3	3	3	4	4	4	cc/dd