[백준] 1074. Z (자바 JAVA)

[ 문제 ]  [백준] 1074. Z (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1074

1074번: Z

---

# 접근 방법 및 풀이 

 

• 분할정복 재귀 문제다. 앞서 다뤘던 "쿼드트리, 색종이 만들기" 문제처럼 그냥 재귀 돌리면 시간초과난다.
• 이유는 N의 범위가 최대 15이므로 2^15 사이즈의 map을 다 잘게잘게 잘라서 r, c를 하나씩 확인한다면 시간초과난다.
• 여기서 중요한건, R, C가 "1, 2, 3, 4" 사분면 중에서 어디범위에 속해있는지 체크해주고 해당 사분면 범위에 속해있다면 그부분만 재귀 돌리면 된다. 
• 다음과 같이 size = 4인, 이차원 map이 있고 R = 1, C = 1의 값을 찾는다고 가정해보자. 

• 0	1	4	5
  2	3	6	7
  8	9	12	13
  10	11	14	15

• (1, 1)은 1사분면에 있고, size /= 2로 1사분면에 대한 재귀를 타면 

• 0	1
  2	3

• 위와 같이size = 2의 사분면으로 또 나뉘어진다. 여기서 (1,1)은 4사분면에 있고, size /= 2로 4사분면에 대한 재귀를 타면

• 3

• size = 1짜리의 1사분면 값만 남는다. 이때 3이 정답이 된다. 따라서 size = 1일 경우 return 조건이 되고 그때 값을 찍어주면된다.
• 그럼 1,2,3,4 사분면에 대한 범위에 대한 if조건이 각각 있을 것이고, 그때마다 map에 들어갈 값을 구해주어야한다.

• 0	1	4	5
  2	3	6	7
  8	9	12	13
  10	11	14	15

• 먼저, map은 2차원배열이기 때문에 size가 4일경우 16가지의 숫자가 들어있고, 시작이 0부터기때문에 0~15까지의 숫자가 들어있다. 
• 이때 만약, 2사분면에 재귀를 탄다고 가정하면, 1사분면의 0~3을 세어주고 4부터 값이 시작해야한다.
• 3사분면의 재귀를 탄다면, 1과 2사분면의 0~7을 세어주고 8부터 값이 시작된다.
• 따라서 각 사분면의 0, 4, 8, 12가 해당 사분면의 시작값이 된다. 각 재귀에서 저 시작값을 구해 갯수에 더해주면 된다.
• 2사분면으로 재귀를 갈 경우, (size*size) / 4 를 더해주면 되고, 3사분면은 ((size*size) / 4) * 2, 4사분면은 ((size*size) / 4) * 3을 더해주면된다.
•  자세한건 코드참조

 

# 주의할 점 

 

• 조건없이 재귀 다 돌리면 시간초과남

 

JAVA 코드

package Silver;

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

public class bj1074_Z {

	static int N, R, C, ans = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		solve(0, 0, (int)Math.pow(2, N));
	}
	private static void solve(int r, int c, int size) {
		if(size == 1) {
			System.out.println(ans);
			return;
		}
		int newSize = size / 2;
		if(R < r + newSize && C < c + newSize ) {
			solve(r, c, newSize);
		}
		if(R < r + newSize && c + newSize <= C) {
			ans += (size*size) / 4;
			solve(r, c+newSize, newSize);
		}
		if(r + newSize <= R && C < c + newSize ) {
			ans += ((size*size) / 4) * 2;
			solve(r+newSize, c, newSize);
		}
		if(r + newSize <= R && c + newSize <= C ) {
			ans += ((size*size) / 4) * 3;
			solve(r+newSize, c+newSize, newSize);
		}
	}
}

 

 

 

REVIEW