백준 1074번 - Z

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

1074번: Z

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

이게 n이 3일때의 방문 순서도이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;



int main() {
	int n;
	int r, c;
	vector< long long > range;
	cin >> n >> r >> c;
	int a = pow(2, n);
	int b = 0;
	int d = pow(2, n);
	int e = 0;
	range.push_back(0);
	range.push_back(pow(2, 2*n)-1);
	while (n>0) {
		long long x = range[1] - range[0] + 1;
		if (r >= (a+b)/2 && c >= (d+e)/2) {
			range[0] = range[0] + 3 * x / 4;
			b = (a + b) / 2;
			e = (d+e) / 2;
		}
		else if (r >= (a + b) / 2 && c < (d + e) / 2) {
			range[0] = range[0] + 2 * x / 4;
			range[1] = range[0] + x / 4 - 1;
			b = (a+b) / 2;
			d = (d+e) / 2;
		}
		else if (r < (a + b) / 2 && c >= (d + e) / 2) {
			range[0] = range[0] + x / 4;
			range[1] = range[0] + x / 4 - 1;
			a = (a + b) / 2;
			e = (d + e) / 2;
		}
		else {
			range[1] = range[0] + x / 4 - 1;
			a = (a + b) / 2;
			d = (d + e) / 2;
		}
		n--;
	}
	cout << range[0];
}

우선 본인은 숫자의 범위를 정해 놓고, n을 줄여가며 사분면에 따라서 수의 위치를 분류하는 방법을 사용했다. r,c의 범위에 따라서 사분면을 정하고, 그 사분면의 숫자들을 범위를 통해 다시 저장해 주는 방법을 사용했다.