[백준1074/C++] Z

1. 문제

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

1074번: Z

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int Z(int N, int r, int c) {
	//base condition
	if (N == 0) return 0;
	int half = pow(2,N) / 2;
	if (r < half && c < half) return Z(N-1, r, c);
	if (r < half && c >= half) return half*half + Z(N - 1, r, c - half);
	if (r >= half && c < half) return 2 * half * half + Z(N - 1, r - half, c);
	if (r >= half && c >= half) return 3 * half * half + Z(N - 1,r - half, c - half);
}

int main(void) {
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int N, r, c;
	cin >> N >> r >> c;
	cout << Z(N, r, c);
}

---

3. 문제 평가 및 해설

재귀를 이용한 문제이다. 재귀 문제는 수학적 귀납법으로 생각하면 편한다. 절차 지향적인 생각보다, "0번째가 되니까, 규칙에 의하면  N번째 조건도 만족하겠지?"라고 생각해야한다. 처음 재귀 문제를 접했을 땐, 까다로울 수 있다. 나도 아직 재귀를 마스터하지 못했지만, 재귀 문제를 풀 땐 나의 머리가 CPU가 되면 안된다. 즉, 일일이 따라가면서 계산하지말고 수학적 귀납법으로 먼저 추측하고 컴퓨터한테 계산을 맡겨야한다. "나의 머리는 CPU가 아니다. 설계하고 계산은 컴퓨터에게 맡기자."를 명심하면서 풀어야 한다.  

본격적으로 문제 풀이를 해보자면,

재귀 문제의 핵심은 수학적 귀납법이다.

해당 맵에서 (7,7)에 해당하는 63를 그나마 쉽게 구하려면 어떻게 해야할까? 

굳이 일일이 세줄 필요없이, 4등분한 사각형이 반복되는 것을 아니까 16*3 를 하고, 첫번째 사각형에서 63과 대응된 위치를 가진 수가 15이니 둘이 더해주면 된다. 그렇다면 15도 일일이 세야할까?

15도 일일이 세어주기 보다는 위에서 했던 방법을 반복하면 되지 않을까? 15와 대응되는 첫번째 사각형의 위치는 3이고, 여기서 4등분한 사각형은 2*2=4로 반복하는 것이니, 4*3 + 3 = 15가 나온다. 재귀적인 느낌이 든다. 63은 15를 참고하고 있고, 15는 3을 참고하고 있다. 함수가 함수를 불러오는 형태이다. base conditon은 N이 0일 때 사각형이 0이 써져있는 1개가 존재할 것이고, 0을 반환할 것이다.

그러면 수학적 귀납법으로 정리해보고, 해당 과정을 코드로 쓰면 된다.

1. Z(0)은 0을 반환한다.

2. Z(K)는 r,k의 위치를 알 수 있다. (풀이 과정에서 r,k를 알 수 있었다.)

3. Z(K+1)도 r,k의 위치를 알 수 있을 것 이다.

 

보통 재귀는 반복적인 부분이 많고, 이전 함수를 불러오는 경향이 있다.

예를 들어, 피보나치 수열은 f(k+2) = f(k+1) + f(k) 의 특징을 가지고 있고, base condtion은 f(1) = 1이다.

하노이탑 역시, n-1개의 원탑을 두번째로 옮기고, 남은 하나를 마지막으로 옮기고, n-1의 원탑을 두번째에서 세번째로 옮기는 과정을 반복했다.

재귀 알고리즘은 실수하면 찾기가 어렵고, 한번에 생각나는 경우가 없으니 많이 연습해야겠다.