BOJ_S1_1074

📁 [S1_1074] Z

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

public class Main {
    static StringTokenizer st;
    static int N, r, c, cnt;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();


        st = new StringTokenizer(br.readLine(), " ");
        // 배열의 크기
        N = Integer.parseInt(st.nextToken());

        // 행
        r = Integer.parseInt(st.nextToken());
        // 열
        c = Integer.parseInt(st.nextToken());

        int temp = (int) Math.pow(2, N);

        dfs(temp, 0,0);
    }

    static void dfs(int n, int x, int y) {
        // 기저조건
        if (x == c && y == r) {
            System.out.println(cnt);
            return;
        }

        // 위치마다 재귀 호출
        if (y <= r && r < (y + n) && x <= c && c < (x + n)) {
            int next_n = n / 2;
            dfs(next_n, x, y);
            dfs(next_n, x + next_n, y);
            dfs(next_n, x, y + next_n);
            dfs(next_n, x + next_n, y + next_n);
        }
        else{
            cnt += n*n;
        }
    }
}

🤔 나의 생각

해당 구역내에 r,c가 속하는지 체크한다. 만약 존재하면 해당 구역을 4등분으로 나눈다.
만약 해당 구역에 속하지 않는다면 해당구역의 크기만큼 탐색한 수에 더해준다 !!
분할 정복 문제이다.