백준 1074 Z (Java)

1. 문제 링크

1074번: Z

 

2. 문제 및 입출력예제

 

3. 문제 풀이

분할정복의 대표적인 문제이다.

4개의 범위로 나눠서 각 범위 안에 들어왔을 때 재귀한다.

점점 작은 범위가 되고 값을 찾게 된다면 size가 1이 되면서 재귀가 끝난다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	private static int visit, R, C;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		R = Integer.parseInt(split[1]);
		C = Integer.parseInt(split[2]);
		
		//2^N x 2^N 배열
		int num = (int)Math.pow(2, N);
		round(R, C, num);

		System.out.println(visit);
	}
	
	static void round(int r, int c, int size) {
		if(size == 1) {
			return;
		}
		
		int half = size/2;
		if(r<half && c<half) {
			round(r, c, half); 
		}
		else if(r<half && c>=half) {
			visit += half*half;
			round(r, c-half, half); 
		}
		else if(r>=half && c<half) {
			visit += half*half*2;
			round(r-half, c, half); 
		}
		else {
			visit += half*half*3;
			round(r-half, c-half, half); 
		}
	}
}