백준 1074 (실버 1) 분할 정복 재귀

이 문제를 보고 어떻게 풀지 생각을 하다가 
이분탐색의 방법을 가로 세로로 중첩해서 풀면 될거 같다는 생각이 들었습니다

 

return 조건은 n이 2일 때 dx, dy를 이용해서 2 * 2 배열을 포문으로 확인합니다

 

 

그런데 그냥 이렇게만 푼다면 시간제한을 벗어날 수가 없습니다 (ㅠㅠ 어림도 없지)

 

어떻게 하면 시간을 단축시킬수 있는지 문제의 그림을 차근차근 다시 보았습니다

 

내가 원하는 행과 열의 값보다 작은 값으로 재귀가 작동한다면 시간이 낭비  된다고 생각했습니다

그래서 재귀의 x, y의 값이 내가 찾고자 하는 행과 열의 값보다 작다면

n * n의 크기를 count에 더해주고 return을 시켜 시간제한을 벗어났습니다.

 

 

#include <iostream>
#include <cmath>

using namespace std;

long long c = 0;

long long xs, r, h;

int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};

void jague(int x, int y , int x2, int y2, int n){
	
	int mid = (x + y) / 2;
	int mid2 = (x2 + y2) / 2;
	
	if(y < r || y2 < h){
		c += n * n;
		return;
	}
	
	if(n == 2){
		
		for(int i = 0; i < 4; i++){
			int nx = mid-1 + dx[i];
			int ny = mid2-1 + dy[i];
			
			if(nx == r && ny == h){
				cout << c;
				exit(0);	
				
				
			}
			
			c++;
		}
		return;
	
	}
	
	jague(x, mid-1, x2, mid2-1, n / 2);
	
	jague(x, mid-1, mid2+1, y2, n / 2);
	

	jague(mid+1, y, x2, mid2-1, n / 2);
	jague(mid+1, y, mid2+1, y2, n / 2);
	
	
	
	return;
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
		
	cin >> xs >> r >> h;
	
	if(xs == 0){
		cout << 0;
		return 0;
	}
	xs = pow(2,xs);
	
	
	jague(1, xs, 1, xs, xs);
	
	
}