[ C / C++ ] 백준 1074 Z

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

 

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

 

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int func(int N, int r, int c)
{
	if (N < 1)
		return 0;

	int mid = (int)pow(2, N - 1);

	if (r < mid && c < mid)
	{
		return func(N - 1, r, c);
	}

	else if (r < mid && c >= mid)
	{
		return mid * mid + func(N - 1, r, c - mid);
	}

	else if (r >= mid && c < mid)
	{
		return mid * mid * 2 + func(N - 1, r - mid, c);
	}

	else
	{
		return mid * mid * 3 + func(N - 1, r - mid, c - mid);
	}
}

int main()
{
	int N, r, c;
	scanf("%d%d%d", &N, &r, &c);

	int result = func(N, r, c);
	printf("%d\n", result);

	return 0;
}