# 생각

N(1<= N <= 15)이 주어졌을 때,

2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 출력하는 프로그램을 작성해야 한다

 

규칙을 보면 배열을 4등분 하여 순서대로 진행하는 것을 알 수 있다

 

base conditino은 n이 0일 때 return해주는게 좋아보인다

 

재귀식은 규칙에 따라 4등분하여 각 상황에 맞게 반환해주면 된다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int ZRecursive(int n, int r, int c)
{
	if (n == 0)
	{
		return 0;
	}
	int half = 1 << (n - 1);
	if (r < half && c < half)	// 왼쪽 위
	{
		return ZRecursive(n - 1, r, c);
	}
	if (r < half && c >= half)	// 오른쪽 위
	{
		return (half * half) + ZRecursive(n - 1, r, c - half);
	}
	if (r >= half && c < half)	// 왼쪽 아래
	{
		return (2 * half * half) + ZRecursive(n - 1, r - half, c);
	}
	else		// 오른쪽 아래
	{
		return (3 * half * half) + ZRecursive(n - 1, r - half, c - half);
	}
}

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

	int N, r, c;
	cin >> N >> r >> c;
	cout << ZRecursive(N, r, c);
}

https://www.acmicpc.net/problem/1074

 

1074번: Z

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

www.acmicpc.net

+ Recent posts