<Algorithm> 58. 1074번 Z

1. 1074번 Z

• 분할 정복 문제, 큰 배열을 4등분씩 작게 분할하여 원하는 값을 찾는 문제, 큰영역을 분할 하다보면 결국 마지막은 하나의 영역이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int count = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        div(N, r, c);
        System.out.println(count);
        
    }
    private static void div(int N, int r, int c) {
        
        if(N == 0) return;
        
        int n = (int)Math.pow(2, N);
        int quarter = n * n / 4;
        // 0 : 1분면,   4 : 2분면,   8 : 3분면,  12 : 4분면 
        // 각 분면의 시작 만큼 더해주고 분할하고 N이 0이될때까지 반복
        
        
        // 0.0 부터 시작하기 떄문에 위쪽 왼쪽이 기준이 된다.
        if(r < n/2 && c < n/2) {
            // 1분면 
            div(N - 1, r, c);
            
        }else if(r >= n/2 && c < n/2) {
            
            // 3분면
            count += quarter * 2;
            div(N - 1, r - n/2, c );
            // 1분면으로 떙기기
            
        }else if(r < n/2 && c  >= n/2) {
            
            // 2분면
            count += quarter;
            div(N - 1, r, c - n/2);
            // 1분면으로 떙기기
        }else if(r >= n/2 && c >= n/2) {
            
            // 4분면
            count += quarter * 3;
            div(N - 1, r - n/2, c - n/2);
            // 1분면으로 떙기기
        }
            
    }
    
}