[BOJ1074][C++] Z

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

1074번: Z

문제

(2^N * 2^N)의 배열을 z 모양으로 탐색하며 (r, c) 자리를 몇 번째에 방문하는지 알아보는 문제이다.

 

해결

처음에는 규칙이 있는 것 같긴한데, 어떻게 구조화시켜야 할지를 몰랐다.

그래서 유튜브 바킹독님의 강의를 참고하였다.

 

🎈Key Point🎈

우선 이 문제는 재귀를 활용해서 풀면 된다. 재귀에서 핵심은 절차지향적 사고를 탈피하고, 1) basic condition이 성립하고 2) K번째가 성립할 때 K+1번째가 성립하면 모든 경우가 성립한다는 귀납적 사고를 가져야 한다.

 

이 문제에서는 어떤 크기의 배열이든 Z모양 순서대로 1,2,3,4의 사각형 네개로 이루어져있다고 생각하고 재귀적 성질을 적용하면 된다. 

 

[전체 코드]

#include <iostream>

using namespace std;



int recursion(int n, int r, int c) {
	// basic condition
	if (n == 0) return 0;

	int half = 1 << (n - 1);	// 2^(n-1)
	if (r < half && c < half) return recursion(n - 1, r, c);	// 1번 사각형
	if (r < half && c >= half) return half * half + recursion(n - 1, r, c - half);	// 2번 사각형
	if (r >= half && c < half) return 2 * half * half + recursion(n - 1, r - half, c);	// 3번 삼각형
	return 3 * half * half + recursion(n - 1, r - half, c - half);	// 4번 사각형
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, r, c;
	cin >> N >> r >> c;

	cout << recursion(N, r, c);
}