백준 1074번 - Z

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

1074번: Z

 

 

 

 

 

이것도 예전에 푼 적이 있는 문제이다. 문제를 딱 보면 재귀를 사용하는 분할정복 문제이다. 하지만 시간 제한이 0.5초로 시간에 유의해야 하는 문제이다. 역시 예전에 풀었을 때, 첫 시도에서 시간 초과가 났었다. 모든 사분면에 대해 재귀를 돌리다가 시간 초과가 났었다.

 

 

 

 

시간 초과가 나지 않기 위해서는 재귀를 돌리기 전에, 내가 탐색하고자 하는 좌표가 어디 사분면에 있는지 먼저 파악을 한 후, 해당 사분면에 대해서만 재귀를 통해 탐색을 해야 한다.

 

ex)

3행 1열 찾기

1. 처음 큰 사각형을 4사분면으로 나눴을 때, 3사분면에 있다. -> 3사분면 탐색

2. 두 번째 사각형을  4사분면으로 나눴을 때, 4사분면에 있다. -> 4사분면 탐색

3. 사각형의 크기가 1이 되어서 종료 -> 결과 리턴

 

 

 

재귀함수의 매개변수로 사각형의 시작 좌표의 행, 열, 사각형 사이즈 정보를 넘겨준다.

그리고 재귀함수 안에서 사분면의 좌표 범위를 계산해, 해당 사분면에 위치하면 재귀를 통해 탐색을 한다.

재귀를 할 때는 사이즈를 반으로 줄인다. 

그리고 사이즈가 1이 되면 재귀를 종료한다.

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int r, c;
	static int count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
	
		int size = (int) Math.pow(2, N);
		
		z(0, 0, size);
		
		System.out.println(count);
	}

	public static void z(int i, int j, int size) {
		if(size == 1) { //종료조건
			return;
		}
		
		if(r < i + size / 2 && c < j + size / 2) { //1사분면에 위치
			z(i, j, size / 2);
		}else if(r < i + size / 2 && j + size / 2 <= c) { //2사분면에 위치
			count += size * size / 4;
			z(i, j + size / 2, size / 2);
		}else if(i + size / 2 <= r && c < j + size / 2) { //3사분면에 위치
			count += size * size / 4 * 2;
			z(i + size / 2, j, size / 2);
		}else { //4사분면에 위치
			count += size * size / 4 * 3;
			z(i + size / 2, j + size / 2, size / 2);
		}	
	}

}

 

 

 

 

 

결과