백준 3163 떨어지는 개미

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

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

 

이 문제는 막대에 개미가 있을 때 개미들이 떨어지는 순서를 구하는 문제입니다. 각 개미들은 이동 방향이 있고 충돌할

경우 방향이 바뀌게 되는데 이문제 같은 경우 충돌을 굳이 고려하지 않아도 되는데 그 이유는 왼쪽과 오른쪽으로 개미들이 떨어질 때 처음의 아이디 순서대로 반드시 떨어지기 때문입니다. 따라서 처음 위치를 입력받은 뒤 방향에 따라 떨어질 때까지 거리를 계산해서 절대값 순서로 정렬을 하였습니다. 그런다음 K번째 떨어지는 개미를 구하면 되는데 이 때 개미가 동시에 떨어 질때는 id가 작은 개미가 먼저 떨어지므로 절대값이 동일한 경우 두 id를 비교해서 swap을 해준 뒤 최종적으로 K번째 개미의 id를 찾아내면 됩니다. 생각보다 잘 안풀려서 아주 오래걸렸습니다,,

 

다음은 코드입니다.

 

#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;
}