[백준 C++] 1074 Z - 분할정복

1074번: Z

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

int N, R, C;
int SearchNum;

void DivideSearch(int StartRow, int StartCol, int Size)
{
	if ((R < StartRow || R > StartRow + Size)
		|| (C < StartCol || C > StartCol + Size))
	{
		SearchNum += Size * Size;
		return;
	}

	if (Size == 2)
	{
		for (int i = StartRow; i < StartRow + Size; ++i)
		{
			for (int j = StartCol; j < StartCol + Size; ++j)
			{
				if (i == R && j == C)
				{
					cout << SearchNum;
					return;
				}

				++SearchNum;
			}
		}

		return;
	}

	DivideSearch(StartRow, StartCol, Size / 2);
	DivideSearch(StartRow, StartCol + Size / 2, Size / 2);
	DivideSearch(StartRow + Size / 2, StartCol, Size / 2);
	DivideSearch(StartRow + Size / 2, StartCol + Size / 2, Size / 2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> R >> C;

	int Size = pow(2, N);
	DivideSearch(0, 0, Size);
}

---

 

재귀 함수를 이용해서 푸는 분할 정복 유형의 문제입니다.

 

N이 큰 수일 때는 모든 구간을 탐색할 경우 시간 초과가 발생할 수 있기 때문에

입력 받은 R, C의 위치가 해당 구간에 포함되는 지를 체크해서

포함되지 않은 구간에서는 Size * Size 만큼 탐색 순서를 더해주고 빠져나오도록 구현하면 됩니다.