BOJ 1074 Z

1074번: Z (acmicpc.net)

1074번: Z

 

우연히 눈에 들어와서 다시 풀어보게 되었다.

3년전에는 시간초과로 풀지 못했었는데, 이번엔 간단히 풀 수 있었다. 

 

요약하자면, 분할정복이다.

Map을 4분할 했을때, r,c의 위치에 따라 r,c보다 앞쪽에서 탐색되는 좌표들의 개수를 대략적으로 알 수 있고, 그 다음 좌표를 shift시키면서 이를 반복한다면, 답을 구할 수 있다.

출처 : boj.kr/1074

각 구역의 좌표들은 다음과 같은 특징을 가진다.

1구역 : r < 2^(n-1), c < 2^(n-1), 1구역의 점들보다 더 빨리 탐색되는 점은 없음

2구역 : r < 2^(n-1), c >= 2^(n-1), 1 구역의 점들 (총 2^(n-1))이 더 빨리 탐색됨

3구역 : r >= 2^(n-1), c < 2^(n-1), 1,2 구역의 점들 (총 2*2^(n-1))이 더 빨리 탐색됨

4구역 : r >= 2^(n-1), c >= 2^(n-1), 1,2,3 구역의 점들 (총 3*2^(n-1))이 더 빨리 탐색됨

 

이를 바탕으로 r,c의 구역을 구하고, 그것보다 더 빨리 탐색되는 다른 구역의 점들을 구한 뒤,

현재 r,c의 구역을 다시 4개의 구역으로 나누어 이를 반복한다면 r,c의 탐색순서가 나오게 된다.

 

코드는 다음과 같다.

#include <cstdio>

int arr[16] = {
  1,2,4,8,
  16,32,64,128,
  256,512,1024,2048,
  4096,8192,16384,32768
};

int main(){

  int n, r, c; scanf("%d%d%d",&n,&r,&c);

  int answer = 0;
  while(n>0){
    
    if(r < arr[n-1] && c < arr[n-1]){
      //empty
    }
    else if(r < arr[n-1] && c >= arr[n-1]){
      answer += arr[n-1]*arr[n-1];
      c -= arr[n-1];
    }
    else if(r >= arr[n-1] && c < arr[n-1]){
      answer += arr[n-1]*arr[n-1]*2;
      r -= arr[n-1];
    }
    else{
      answer += arr[n-1]*arr[n-1]*3;
      c -= arr[n-1];
      r -= arr[n-1];
    }
    --n;
  }

  printf("%d\n",answer);

  return 0;

}

 

시간복잡도는 O(N) 이다.

 

 

다 풀고나서 3년전의 코드를 보니 그당시에는 분할정복 & 완탐 으로 이 문제를 풀려고 했던 것 같다.

아마 시간내에 들어올 수 있을거라는 예상으로 풀었는데, 안풀려서 그만 둔 것 같다.

그당시 코드는 다음과 같다.

#include <cstdio>
#include <cmath>
int r,c; //int arr[r][c]
int a = 0;
int dnc(int r1, int c1, int r2, int c2){
	//printf("%d %d %d %d\n",r1,c1,r2,c2);
	int count = 0;
	bool flag = false;
	if(r2- r1 == 1 && c2-c1 == 1){
		if(r1 == r && c1 == c){
			count = 1;
		}
		else if(r1 == r && c2 == c){
			count = 2;
		}
		else if(r2 == r && c1 == c){
			count = 3;
		}
		else if(r2 == r && c2 == c){
			count = 4;
		}
		else
			return 4;
		a = 1;
		return count;
	}
	else{
		//int b = (r2/2 + 1 - r1)*(c2/2+1-c1);
		//if((c2-c1)/2+c1 <= c || r1 <= r)
		if(a == 0) count += dnc(r1,c1, (r2-r1)/2 + r1, (c2-c1)/2+c1);
		//if(c2 <= c || r1 <= r)
		if(a == 0) count += dnc(r1,(c2-c1)/2+c1+1, (r2-r1)/2+r1,c2);
		//if((r2-r1)/2+r1+1 <= r || (c2-c1)/2+c1 <= c)
		if(a == 0) count += dnc((r2-r1)/2+r1+1,c1, r2,(c2-c1)/2+c1);
		//if((r2-r1)/2+r1+1 <= r || c2 <=c )
		if(a == 0) count += dnc((r2-r1)/2+r1+1,(c2-c1)/2+c1+1, r2,c2);
 
		return count;
	}
 
 
}
 
 
int main(){
	int n; scanf("%d%d%d",&n,&r,&c);
 
	printf("%d",dnc(0,0,pow(2,n)-1,pow(2,n)-1)-1);
 
 
 
}