[BOJ] 1074번 : Z (C++)

📖 백준 1074번 : https://www.acmicpc.net/problem/1074

조건

시간 제한	메모리 제한
0.5 초 (추가 시간 없음)	512 MB

문제

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

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N, r, c가 주어진다.
1 ≤ N ≤ 15
0 ≤ r, c < 2N

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

---

풀이

 먼저 가장 단순하게 푸는 방법으로 2^(2N)번 반복해서 브루트포스하는 방식을 생각했다. N이 최대 15까지 주어지므로, 단순하게 풀면 10억번 이상의 계산이 필요해서 제한 시간을 넘기게 된다. 따라서 배열을 만들거나 일일이 반복하는 것을 제외했다.

 문제에서 답이 z모양으로 재귀적으로 반복해서 증가하는 모습을 보고 2^(2N)번 반복하는 것이 아니라, n+1번 반복하는 방법으로 모든 경우를 나눌 수 있겠다는 판단을 했다.

 총 4가지 케이스를 사분면의 형태로 나눠서 생각했다. row, col이 2^(n-1)을 기준으로 큰지 작은지를 판단해서 어떤 사분면에 포함되는지 파악하고 이를 반복 수행한다. 이 때 포함되는 사분면의 가장 왼쪽위의 값 즉, 시작하는 값을 계산했다. n이 0이되는 시점까지 반복해주고 값을 출력하면 끝이다.

Z를
0 1
2 3 <- 이런 모양으로 생각했다.

코드

#include <iostream>
#include <cmath>

using namespace std;

void Z(int n,int row, int col, int startValue) {
	if (n == 0) 
		cout << startValue;
	else {
		int t = pow(2, n - 1);
		int t2 = t * t;

		if (t > row) {
			if (t > col) // 0번 위치
				Z(n - 1, row, col, startValue);
			else // 1번 위치
				Z(n - 1, row, col - t, startValue + t2);
		}
		else {
			if (t > col) // 2번 위치
				Z(n - 1, row - t, col, startValue + t2 * 2);
			else // 3번 위치
				Z(n - 1, row - t, col - t, startValue + t2 * 3);
		}
	}
}

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

	int n, r, c;
	cin >> n >> r >> c;
	Z(n, r, c, 0);

	return 0;
}