[백준 BOJ] 1074 : Z (C++)

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

1074번: Z

어떻게 보면 그냥 구현이라고 볼 수 있을 것 같은데, 그래도 이 문제 같이 재귀가 핵심 아이디어인 문제들은 조금 다른 느낌이 있어서 재귀 카테고리로 따로 모은다

#include <iostream>
using namespace std;

int func(int n, int r, int c) {
	// base condition
	if (n == 0) return 0;

	// 0, 1, 2, 3 section 중 어디에 속하는지에 따라 구분하여 재귀호출을 구분지을 것.
	// 호출할 때마다 r과 c가 base condition에 수렴하도록 작성
	// 예를 들어 현재 (r, c) 위치가 2번 section에 있다면, 
	// 0, 1 번 section의 정사각형 개수 만큼은 이미 탐색을 하고 온 것이므로,
    // 2 * 정사각형넓이 = 2 * (half * half) 를 해준 것
	int half = 1 << (n - 1); // 0001 을 n만큼 left shif한다는 의미이므로 2^(n - 1) 을 의미
	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);
	return 3 * (half * half) + func(n - 1, r - half, c - half);
}

int main() {
	int n, r, c;
	cin >> n >> r >> c;

	cout << func(n, r, c) << '\n';
}

https://www.youtube.com/watch?v=8vDDJm5EewM 

재귀가 핵심 아이디어인 문제는 정말 샘플을 보지 않고는 도저히 첫 시도에 알고리즘을 떠올릴 수가 없어서 바킹독님 영상을 통해 공부 후 샘플로 말씀해주신 몇 문제를 먼저 보았다.

코드를 먼저 보고 나니 재귀가 어떤 느낌으로 코드를 작성해야하는지 감은 오는데, 여타 문제와 같이 '아 이 유형은 문제를 읽었을 때 이러한 특징을 가지고, 이렇게 접근을 먼저 시작해야겠다' 는 일반화가 머리에 잘 서질 않는다.

앞으로 문제를 더 많이 풀어봐야할 것 같다.