[S1] Z : 1074 - 분할정복

1. 💎 문제

 

 

 

2.  🤔 어떻게 풀까

`찾을 때까지 재귀`를 돌리면 될 것 같다. 어떤 조건으로 재귀를 돌릴까?

찾아야 되는 숫자를 기준으로 x, y값 범위가 초과되는지, 포함되는지 여부에 따라 `4사분면`으로 나눠서 진행한다. 

만약 현재 탐색하는 x의 범위가 찾아야 하는 x값보다 크다면 2, 3 사분면으로 인식하여 더해줄 것 더해주고 y값도 마찬가지로 비교해서 적절한 사분면을 찾자, 범위는 현재 범위의 나누기 2만큼 다시 탐색을 진행! 그리고 원하는 값을 찾으면 재귀를 멈춘다.

 

문제를 잘못 봐서 원하는 숫자를 기준으로 로직을 생각했다가, 주어지는 것이 행과 열 정보인 것을 보고 기준을 행과 열로 다시 진행했다! 로직은 같다.

 

 

3.  🖥️ 코드

여기서의 제4사분면은 지그재그 순서대로 1,2,3,4 분면을 나눴다.

제 2사분면이면 제 1사분면에 있는 좌표의 크기인 `2의 N-1승* 2의 N-1승`만큼 더하고 제 3사분면이면 제 1사분면과 제 2사분면의 좌표만큼 `ans`에 더한다. 

import java.util.Scanner;
import java.util.StringTokenizer;

class Solution
{
	
	static int r = 0;
	static int c = 0;
	static long ans = 0;
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(sc.nextLine());
		
		int N = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		solution(N,0,0);
		
		System.out.println(ans);
		
	}
	
	public static void solution(int N, double row, double col) {
		boolean isRowOver = false;
		boolean isColOver = false;
		
		if(N == 0 || row == r && col == c)
			return;
		
		if(r >= row + Math.pow(2, N-1)) {
			isRowOver = true;
		}
		if(c >= col + Math.pow(2, N-1)) {
			isColOver = true;
		}
		
		// 1사분면
		if(!isRowOver && !isColOver) {
			solution(N-1, row, col);
		}
		// 2사분면
		else if(!isRowOver && isColOver) {
			ans += Math.pow(2, N-1)* Math.pow(2, N-1);
			solution(N-1, row, col +  Math.pow(2, N-1));
			
		}// 3사분면
		else if(isRowOver && !isColOver) {
			ans += Math.pow(2, N-1)*Math.pow(2, N-1)*2;
			solution(N-1, row +  Math.pow(2, N-1), col);
			
		}// 4사분면
		else if(isRowOver && isColOver) {
			ans += Math.pow(2, N-1)*Math.pow(2, N-1)*3;
			solution(N-1, row +  Math.pow(2, N-1), col +  Math.pow(2, N-1));
		}
		
	}
}