백준 1074번 : Z [분할정복][재귀] -Java

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

1074번: Z

분할정복은 패턴을 파악하여 하나의 큰 문제를 작은 부분 문제로 쪼개서 각각 계산하고 이들을 합하여 답을 구한다.

 

N=3이면, 2^N* 2^N 배열이 생긴다.

노란색 음영인 (5,4)의 방문순서를 구한다고 할때, 

재귀는 2^(N-1)* 2^(N-1)로 4등분하므로 2^2 * 2^2 => 4*4가 된다.

 

 

4*4 크기만큼 4등분 해서 보면 (5,4)의 위치는  1,2,3,4번째중 4번째로 속하게 된다.

 

그러면 나머지 1,2,3은 모두 다 방문해야하므로 4*4*3 을 통해서 한번에 방문 횟수를 구하고

나머지 4번째 화면에 대한 재귀를 수행한다.

N-1하여 아까와 마찬가지로 1,2,3,4 번째 확인하여 재귀 수행..

이번에는 1번째에 존재하기에 별도 덧셈없이 다시 쪼갠다. 

 

 

<Java 코드>

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

public class Main {

	public static int N;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		int row = Integer.parseInt(st.nextToken());
		int col = Integer.parseInt(st.nextToken());

		System.out.println(fun(N, row, col));

	}

	public static int fun(int n, int r, int c) {

		int sum = 0;
		if (n > 0) {
			
			int mid = (int) Math.pow(2, n) / 2;
			
			if (r < mid && c < mid) {
				sum += fun(n - 1, r, c);
			} else if (r < mid && c >= mid) {
				sum += (mid * mid) + fun(n - 1, r, c - mid);
			} else if (r >= mid && c < mid) {
				sum += (mid * mid * 2) + fun(n - 1, r - mid, c);
			} else {
				sum += (mid * mid * 3) + fun(n - 1, r - mid, c - mid);
			}
		}
		return sum;
	}

}