[BOJ][JAVA] 1074 - Z

문제 출처: https://www.acmicpc.net/problem/1074

1074번: Z

 

 

 

 

문제

 

 

 

 

설명

전형적인 이분탐색 문제인데, 이런 류의 문제는 처음 만나봐서 헤멨던 문제입니다.

직관적으로 떠오르는 풀이법인 2차원 배열로 풀었을 경우, 배열의 사이즈가 2의 30제곱까지 올라가기 때문에 무조건 메모리 초과가 일어납니다.

그렇기 때문에 반드시 이분탐색으로 풀어야 하며, 찾아야 하는 r,c좌표가 어느 사분면에 있는지를 알아낸 다음 그 전 사분면들은 값만 더해줄 뿐 더 이상 고려하지 않고, r,c가 속해있는 사분면을 다시 4등분하여 r,c의 위치 범위를 점점 좁혀 갔습니다. 이 로직을 재귀적으로 반복하는 형식으로 풀었습니다. 

 

 

 

 

코드

import java.util.Scanner;

public class BOJ1074_Z1 {

	static int N, R, C;
	static int cnt;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); 
		R = sc.nextInt(); //행 번호
		C = sc.nextInt(); //열 번호
		
		solution((int)Math.pow(2, N), 0, 0);
	}
	
	private static void solution(int n, int x, int y) { // n:한 변의 길이 x, y : 탐색을 시작하는 좌표
		
		if(R==x && C==y) { //탐색한 위치가 찾으려는 그 위치라면
			System.out.println(cnt);
			return;
		}
		
		//앞 두 조건을 넣어주지 않으면 메모리 초과가 뜸.
		if(x<=R && y<=C && R<(x+n) && C<(y+n)) { //R과 C가 범위 안에 있다면 -> 4분면으로 쪼개들어 가서 탐색
			int half = n/2;
			
			solution(half, x, y); //1사분면 탐색
			solution(half, x, y+half); //2사분면 탐색
			solution(half, x+half, y); //3사분면 탐색
			solution(half, x+half, y+half); //4사분면 탐색
		} else { //R과 C가 범위 안에 없다면 
			cnt += n*n; //그냥 값을 계산해서 더해줌.
		}
	}
}