[ 백준 1074 JAVA ] Z (Feat. 분할정복)

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

1074번: Z

 

Solve

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

public class Main {
	
	static int n, r, c, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		partition(0, 0, (int) Math.pow(2, n));	
	}
  
	static void partition(int i, int j, int size) {
		if (size == 1) {
			System.out.println(ans); // 결과 출력 
			return;
		}
		
		int newSize = size / 2;
		if (r < i + newSize && c < j + newSize) 
			partition(i, j, newSize);
		if (r < i + newSize && j + newSize <= c) {
			ans += (size * size) / 4;
			partition(i, j + newSize, newSize);
		}
		if (i + newSize <= r && c < j + newSize) {
			ans += (size * size) / 4 * 2;
			partition(i + newSize, j, newSize);
		}
		if (i + newSize <= r && j + newSize <= c) {
			ans += (size * size) / 4 * 3;
			partition(i + newSize, j + newSize, newSize);
		}
	}
}

 

Review

평범하게 재귀를 돌리면 메모리 초과가 발생한다. 

4분면을 구분하여 입력받은 좌표가 4분면 중 어느 위치인지를 확인해서 재귀를 1/4만 돌릴 수 있도록 하여 에러를 해결했다. 

결과 출력도 main 함수가 아닌 재귀함수에서 size==1일 때 출력해야 한다.