[BOJ / C++] Z (재귀)

문제링크: https://www.acmicpc.net/problem/1074

 

1. 코드

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

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

	int center = (1<<n) / 2;

	if (r < center && c < center) return func(n-1, r, c);
	else if (r < center && c >= center) return center*center + func(n-1, r, c-center);
	else if (r >= center && c < center) return 2*center*center + func(n-1, r-center, c);
	else if (r >= center && c >= center) return 3*center*center + func(n-1, r-center, c-center);
}

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

	int n, r, c;
	cin >> n >> r >> c;

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

 

2. 분석

n=3일때 Z

n=3일 때 가로, 세로는 2^3=8이고 center 4를 기준으로 4등분 할 수 있다. 4등분 했을 때 좌상부가 기준이 되고, 순서대로 우상부는 center*center + 좌상부에 대응된다. 좌하부는 2*center*center에 대응되고, 우하부는 3*center*center에 대응된다. 이를 재귀식으로 잘 분리해서 호출해주면 된다.

 

3. 시간복잡도

재귀 호출을 이용했고, 재귀의 깊이는 n에 비례한다. 각각에서 재귀호출은 한번씩만 일어나므로 총 n번 호출이 일어나고 시간복잡도는 O(n)이다.