[ C++ ] #1074 Z

 

찾으려는 값이 들어간 2*2 박스의 첫 칸만 안다면
찾으려는 값도 쉽게 찾을 수 있다
순서가 필요하기 때문에 고민이 되는 문제이다
 
먼저 제일먼저 생각나는건! 재귀로 배열을 채우고 주어진 배열의 값을 출력하는것이다!
하지만 이런 방법은 너무 비효율적일 것 같다.
2의 15승까지 될 수 있는데..이는너무 오래걸린다.
 
그래서 생각해본건 4개로 나누고 찾으려는 숫자가 있는 범위를 4칸 중에 한 칸를 선택하고,
또 그 한 칸을 4개로 나누고 범위를 찾고 하면서 구체화 시키면 될 것 같다.
 
정리하자면 전체 칸을 4칸으로 나누고 각 칸은 그 칸의 제일 앞에있는 수로 관리하는 것이다.
각 칸의 맨 앞에 있는 수의 좌표와 값을 알아야하는데, 규칙을 찾아보면 다음과 같이 된다는 것을 알 수 있다. 
Z함수는 a,b점이 대표인 n*n 칸에서 찾으려는 칸을 return하는 함수이다.
아래 그림 좌표대로 다음 재귀함수를 돌리면 되고,
아래 그림 값을 리턴해주면 된다. 
 

재귀

#include<iostream>

using namespace std;

int A, B,N;

int power(int n, int k) {
	if (k == 0) return 1;
	return n * power(n, k - 1);
}

int Z(int x, int y, int n) {


	if (n == 0) {
		return 0;
	}

	int k = power(2, n - 1);
	
	if (x <= A && A < k+x  && y <= B && B < k +y) {  //1
		return Z(x, y, n - 1);
	}
	else if (x <= A && A < k +x && k+y <= B && B < y+2*k) { //2
		return k*k+Z(x, y + k, n - 1);
	}
	else if (x+k <= A && A < x+k*2  && y <= B && B < k +y) {  //3
		return 2*k*k + Z(x + k, y, n - 1);
	}
	else { //4
		return 3 * k * k + Z(x + k, y + k, n - 1);
	}


}

int main() {

	cin >> N >> A >> B;

	cout<<Z(0, 0, N);

}