백준 1074 Z C++ // 재귀

https://www.acmicpc.net/problem/1074

1074번: Z

1. 왜 재귀로 푸나?

새로운 값을 구할때 이전의 값을 활용한다.

 

2. 함수정의 

3. 기저사례

4. 재귀식

#include <bits/stdc++.h>
using namespace std;

//2^n * 2^n 배열에서 , (r,c) 방문순서 반환
int func(int n, int r, int c) {
	//기저사례 : 1x1 칸의 번호는 0이다.
	if (n == 0) return 0;
	int half = 1 << (n - 1);	//2^(n-1)임.

	//좌측위의경우
	//이전구역이 총 몇칸인지 해당 값 + 다시4분할해서 재귀
	if (r < half && c < half) {
		return func(n - 1, r, c);
		
	}
	if (r < half && c >= half) {
		return half * half + func(n - 1, r, c - half);
		
	}
	if (r >= half && c < half){
		return 2 * half * half + func(n - 1, r - half, c);
	}
	if (r >= half && c >= half) {
		return 3 * half * half + func(n - 1, r - half, c - half);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);

	int n, r, c;
	cin >> n >> r >> c;
	cout << func(n, r, c);

	return 0;
}