백준 1074 Z

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 크기가 2*2 일때 Z모양으로 각 원소를 탐색하는 배열이 있을 때 주어진 크기의 배열에서 r,c에 해당하는 원소를 몇번째로 방문하는지 구하는 문제입니다. 배열의 크기는 2^N * 2^N 이므로 한번 쪼개질때 4등분이 나고 총 배열의 크기는 N이 15까지 가능하므로 32768*32768의 어마어마한 크기가 됩니다. 따라서 배열을 정의해서 풀 수는 없고 저는 r,c가 존재하는 범위의 구역까지 쪼개면서 그이전에 방문지점들을 더해주는 방식으로 풀었습니다.

 

예를들어    4*4 배열이 있을때 제일 끝점인 15,15 에 원소가 존재한다면 처음에 2*2 4개로 쪼개지고 가장 오른쪽 아래에 있는 2*2 배열의 범위안에 r,c가 있음을 알 수 있습니다. 따라서 이전에 존재하는 4*3만큼을 더해주고 진행중인 배열안에서 Z모양으로 값을 더해주면 원하는 값을 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int arr[31][31];
int seq;
int N,r,c;

void search(int start, int end) {
	for(int i = start; i < start+2; i++) 
		for(int j = end; j < end+2; j++) {
			if(i == r && j == c) {
				cout<< seq;
			}
			seq++;
		}
}

bool check(int x, int y, int n) {
	int rootn = sqrt(n) - 1;
	
	if(x <= r && x+rootn >= r && y <= c && y+rootn >= c)
		return true;
	
	return false;
}

void divide(int startx,int starty, int n) {
	int rootn = sqrt(n);
	int midx = (startx + startx+rootn-1) / 2;
	int midy = (starty + starty+rootn-1) / 2;
	
	if(n == 4) {
		search(startx, starty);
	}
	else {		
		if(check(startx, starty, n/4))
			divide(startx, starty, n/4);
		if(check(startx, midy+1, n/4)) {
			seq = seq + n/4;
			divide(startx, midy+1, n/4);
		}
		if(check(midx+1, starty, n/4)) {
			seq = seq + n/4*2;
			divide(midx+1, starty, n/4);
		}
		if(check(midx+1, midy+1, n/4)) {
			seq = seq + n/4*3;
			divide(midx+1, midy+1, n/4);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> r >> c;
	int size = pow(2, N);
	size = size * size;
	divide(0,0, size);
	
	return 0;
}