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

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

---

이 문제는 분할정복으로 쉽게 풀 수 있는 문제이다. 

그리고 배열을 만들필요가 없다. 

굳이 만들겠다면 확인해 보자 heap 메모리가 부족하다고 에러가 발생할것이다. 

입력값이 최대 값이 15 이다 이 15가 15 X 15 가 아니라 2의 15승이다 

2의 15승은 32,768이다. 

그럼 32,768 * 32,768 = 1,073,741,824

10억개 정도 나온다. 그럼 이것또한 무식하게 재귀로 풀것인가?? 그것또한 미친짓이다. 

이 문제의 정답 비율은 굉장히 높다.

그럼 쉽게 접근 할 수 있다는것이다. 

배열의 크기를 최소 사이즈인 2가 될때까지 계속 4등분을 하면서 입력받은 좌표가 범위 안에 있는 것들만 계산을 했다. 

8*8 배열에 (2, 5) 좌표의 방문 순서를 확인 하고자 할때 8*8 배열을 4등분 하고 

최소 사이즈가 됐을때 방문 횟수를 계산하는것으로 소스를 작성했다. 

소스

import java.util.Scanner;
 
public class Main {
    
    public static int row;
    public static int col;
    
    public static int[] dy = {0, 0, 1, 1};
    public static int[] dx = {0, 1, 0, 1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int pow = sc.nextInt();
        
        int size = (int) Math.pow(2, pow);
        row = sc.nextInt();
        col = sc.nextInt();
        
        drawZ(0, 0, 0, size);
        
        sc.close();
        
        System.out.println(size*size);
    }
    
    public static void drawZ(int y, int x, int cnt, int size) {
        // 확인하고자 하는 row와 col 좌표가 y <= row < y+size, x <= col < x+size 범위 에 해당되지 않으면 구할 필요 없다. 
        if(y > row || y+size <= row || x > col || x+size <= col) return;
        
        if(size == 2) {
            
            for(int i=0; i < 4; i++) {
                int yy = dy[i] + y;
                int xx = dx[i] + x;
                
                if(yy == row && xx == col) System.out.println(cnt + i);
            }
            return;
        }
        
        int newSize = size/2;
        
        drawZ(y, x, cnt, newSize);
        
        drawZ(y, x+newSize, cnt+(newSize*newSize), newSize);
        
        drawZ(y+newSize, x, cnt+(newSize*newSize*2), newSize);
        
        drawZ(y+newSize, x+newSize, cnt+(newSize*newSize*3), newSize);
    }
}