[기출 중] 백준 1074 Z

[문제]

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

1074번: Z

 

[풀이]

분할정복 문제이다. 현재 사분면 내에 r행 c열이 존재하면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀적으로 탐색해준다. 만약 현재 사분면 내에 r행 c열이 없으면 그 사분면 크기(width*width) 만큼을 탐색 순번(횟수)에 더해주어야 한다. 

 

[코드]

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

int n, r, c;
int width, x, y;
int cnt;
void solution(int y, int x, int width) {
	if (x == c && y == r) {
		cout << cnt;
		return;
	}
	if (x + width > c && x <= c && y + width > r && y <= r) { //현재 사분면 내에 r행 c열이 존재하면
		solution(y, x, width / 2); // 왼쪽 위
		solution(y, x + width/2, width / 2); // 오른쪽 위
		solution(y + width/2, x, width / 2); // 왼쪽 아래
		solution(y + width / 2, x + width / 2, width / 2); //오른쪽 아래
	}
	else { //존재하지 않으면 현재 사분면의 크기만큼 탐색한 것으로 간주하고 cnt에 더해줌.
		cnt += width * width;
	}
}

int main() {
	//분할정복. 재귀적. 2^n x 2^n, r행 c열을 몇번째로 방문하는지.
	cin >> n >> r >> c;
	//왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
	int width = 1;
	for (int i = 0; i < n; i++)
		width *= 2;
	solution(0, 0, width);

	return 0;
}