언제나 처음처럼

[문제 링크]

2^N X 2^N 크기의 보드가 주어졌을 때, 이를 4등분 하면 2^(N-1) X 2^(N-1) 보드 4개로 나뉘게 된다.

또한 입력받은 좌표는 반드시 4개의 보드 중 한개의 보드 내에 존재하게 된다. 입력받은 좌표를 포함하는 보드에 대해 계속 나누면서 나뉜 보드의 크기가 2^1 X 2^1 이 되었을 때, 선택된 2X2 크기의 보드에는 반드시 입력받은 좌표가 존재하게 된다.

좌표와 일치하는 블록이 전체 보드판에서 가지는 값(방문 순서)을 출력해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cmath>
using namespace std;

int Solution(int N, int col, int row, int start, int findCol, int findRow)
{
	if (N == 1)
	{
		if (col == findCol && row == findRow) return start;
		else if (col == findCol && row + 1 == findRow) return start + 1;
		else if (col + 1 == findCol && row == findRow) return start + 2;
		else return start + 3;
	} 

	int halfCol = pow(2, N) / 2 + col;
	int halfRow = pow(2, N) / 2 + row;

	if (findCol < halfCol && findRow < halfRow)
		return Solution(N - 1, col, row, start, findCol, findRow);

	else if (findCol < halfCol && findRow >= halfRow)
		return Solution(N - 1, col, halfRow, start + pow((pow(2,N)/2),2), findCol, findRow);

	else if (findCol >= halfCol && findRow < halfRow)
		return Solution(N - 1, halfCol, row, start + pow((pow(2, N)/2), 2) * 2, findCol, findRow);

	else
		return Solution(N - 1, halfCol, halfRow, start + pow((pow(2, N)/2) , 2) * 3, findCol, findRow);
}

int main(void)
{
	int N, r, c;
	cin >> N >> r >> c;
	cout << Solution(N, 0, 0, 0, r, c) << endl;
}

알고리즘 200일 프로젝트 - 37day