백준 / 1074 Z C++

www.acmicpc.net/problem/1074

1074번: Z

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 Z모양처럼 이어나간다고 할 때 주어진 위치는 몇번째로 가느냐의 문제입니다. n, r, c가 주어졌을 때, 2^n개의 정사각형이 주어지고, 2^(n-1)을 기준으로 4등분합니다. 그리고 주어진 r, c가 

2^(n-1) 과 비교하여 4등분 중 어느 위치에 있는지를 파악하고 r, c값을 변경해주면 됩니다. 

그와 동시에 기준점을 왼쪽 위 첫 번째 수로 잡은 뒤 정사각형 변이 1이 될 때까지 재귀적으로 해쳐나가면 됩니다. 

 

코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>

using namespace std;

int n, r, c;
int order[2][2] = { {0,1},{2,3} }; // {왼 위, 오른 위},{왼 아래, 오른 아래}

int func(int n, int r, int c, int first) // first : 제일 왼쪽 위의 값 (기준)
{
	if (n == 1)
		return first + order[r][c];

	int half = pow(2, n - 1); // 절반 위치를 기준으로
	int last = pow(2, n); // 정사각형 크기
	int diff = half * half; // 기준 업데이트 용도

	if (r >= 0 && r < half) {
		if (c >= 0 && c < half) {
			return func(n - 1, r, c, first);
		}
		else if (c >= half && c < last) {
			return func(n - 1, r, c - half, first + diff);
		}
	}
	else if (r >= half && r < last) {
		if (c >= 0 && c < half) {
			return func(n - 1, r - half, c, first + diff * 2);
		}
		else if (c >= half && c < last) {
			return func(n - 1, r - half, c - half, first + diff * 3);
		}
	}

}

int main()
{
	cin >> n >> r >> c;
	int result = func(n, r, c, 0);
	cout << result;
}