백준 / 바킹독님의 문제집 / Z(1074)

---

문제 설명

문제 해결

일단 시간 제한이 0.5초로 매우 짧다.

배열을 선언하여 재귀적으로 Z 모양으로 순회한다면 시간 제한에 걸릴 것 같다.

N이 15라면 배열의 크기는 $2^{15} \times 2^{15}$ 정도까지 커지기 때문이다.

저 정도 시간 제한이라면 순회가 아니라 단순 연산 정도로 끝나야 알맞을 것 같다.

그렇다면 순회하지 않고도 r행 c열을 몇 번째로 방문했는지 알 수 있을까?

N이 2인 배열을 탐색하려고 하고, r이 1, c가 2라면 6이라는 숫자를 어떻게 만들 수 있을까?

$2^{N-1} \times 2^{N-1} + f(N-1,r,c - 2^{N-1})$ 요런 형태로 재귀해주면 될 것 같다.

r이 2이고 c가 1이라면 9라는 숫자를 어떻게 만들 수 있을까?

$2 \times 2^{N-1} \times 2^{N-1} + f(N-1,r- 2^{N-1},c)$ 요런 형태로 재귀해주면 될 것 같다.

r이 2이고 c가 2라면 12라는 숫자를 어떻게 만들 수 있을까?

$3 \times 2^{N-1} \times 2^{N-1} + f(N-1, r - 2^{N-1}, c-2^{N-1})$ 요런 형태로 재귀해주면 될 것 같다.

즉, 각 경우의 수에 따라서 다른 형태로 재귀하면 된다.

#include <iostream>
#include <queue>
#include <utility>
#include <tuple>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <algorithm>

using namespace std;

int z_search(unsigned int N, unsigned int r, unsigned int c)
{
	if (N == 0)
		return 0;

	unsigned int half = 1 << (N - 1);

	if (r < half && c < half) 
		return z_search(N - 1, r, c);
	if (r < half && c >= half) 
		return half * half + z_search(N - 1, r, c - half);
	if (r >= half && c < half) 
		return 2 * half * half + z_search(N - 1, r - half, c);

	return 3 * half * half + z_search(N - 1, r - half, c - half);
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	int N, r, c;
	cin >> N >> r >> c;

	cout << z_search(N, r, c) << '\n';

	return 0;
}

---

Uploaded by Notion2Tistory v1.0.0