[백준] 1074번: Z [C++]

 

알고리즘 분류: 분할 정복, 재귀

문제 링크: https://www.acmicpc.net/problem/1074

1074번: Z

 

 

【 풀이 】

 

중학교 때 배운 좌표와 그래프에서 '사분면'이란 개념을 생각하면, 배열을 이용하지 않고도 쉽게 해결 가능하다.

 

일단 이 문제는 배열에 접근하는 식으로는 해결하기 힘들다. 이 문제에서의 최댓값인 2의 15 제곱은 32768이고, 32768의 제곱은 1억이 넘어가기 때문이다.

따라서 이 문제는 분할, 정복으로 배열을 계속 쪼개가면서, 입력으로 주어진 행과 열에 해당하는 숫자를 직접 계산해서 출력해야 한다.

 

(0, 0) 좌표를 기준으로 제1사분면, 제2사분면, 제3사분면, 제4사분면이 나누어지는 개념을 알고 있을 것이다.

이 문제도 4로 나누어 떨어지는 2차원 배열만 사용하기에, 가운데 좌표를 기준으로 4개의 사분면을 나눌 수 있다.

그리고 예제 그림을 보면 한 칸 한 칸이 Z 모양으로 움직이는 것은 물론, 전체적으로도 Z 모양으로 움직인다.

따라서 한 변을 N이라 했을 때 가운데 좌표는 (N/2, N/2)가 되고 이런 식으로 사분면을 정의할 수 있다.

그렇다면 구하고자 하는 행과 열이 주어졌을 때, 나머지 3개의 사분면은 걸러내고 해당하는 사분면을 다시 4 분할하는...

입력으로 주어진 행과 열에 해당하는 사분면만 계속 걸러내면 된다.

 

예를 들어 입력으로 N = 3, r = 7, c = 7 이 주어졌다고 가정하자.

그러면 한 변의 길이가 2^3 = 8 인 배열이 만들어지고, 중심 좌표는 (4, 4)이다. 구하고자 하는 (7, 7)은 4분면에 존재한다.

그리고 4분면을 다시 분할하면 중심 좌표는 (2, 2)

구하고자 하는 값은 중심 좌표를 뺀 (7 - 4, 7 - 4), 즉 (3, 3)이 된다. 그리고 이 값은 다시 4분면에 존재한다.

또다시 분할하면 중심 좌표는 (1, 1)

구하고자 하는 값은 (3 - 2, 3 - 2), 즉 (1, 1)이 되어서 4분면에 존재한다.

한 변의 길이가 2까지 왔으니 더 이상 분할하지 못한다.

 

그렇다면 나누지 못할 때까지 분할했을 때의 숫자는 어떻게 구해야 할까?

숫자를 잘 보면 규칙이 존재한다.

위 그림은 N = 2 일 때, 4 * 4 크기의 배열이다.

각 사분면들을 4 분할했을 때의 첫 번째 수는

 

1 사분면: (4 * 4) / 4 * 0,

2 사분면: (4 * 4) / 4 * 1,

3 사분면: (4 * 4) / 4 * 2,

4 사분면: (4 * 4) / 4 * 3 이다.

 

즉 (4 * 4) / 4 이 부분이 1이 될 때까지 계속 분할하면 된다.

 

이 공식에 따르면 위의 예시의 답은 63이 된다.

 

 

 

 

【 코드 】

#include<iostream>
#include<cmath>
using namespace std;

int num;
int n, r, c;

void div(int r, int c, int n) {
	int temp = pow(n, 2) / 4;
	int y = n / 2;
	int x = n / 2;
	// 1
	if (r + 1 <= y && c + 1 <= x) {
		num += temp * 0;
		if (temp == 1) return;
		div(r, c, n / 2);
	}

	// 2
	if (r + 1 <= y && c + 1 > x) {
		num += temp * 1;
		if (temp == 1) return;
		div(r, c - x, n / 2);
	}

	// 3
	if (r + 1 > y && c + 1 <= x) {
		num += temp * 2;
		if (temp == 1) return;
		div(r - y, c, n / 2);
	}

	// 4
	if (r + 1 > y && c + 1 > x) {
		num += temp * 3;
		if (temp == 1) return;
		div(r - y, c - x, n / 2);
	}
}

int main() {
	int N;
	cin >> n >> r >> c;

	N = pow(2, n);

	div(r, c, N);

	cout << num;

	return 0;
}