[백준/JAVA] 1074번 Z - 분할 정복, 재귀

풀이

모든 경우의 수를 다 세면?

시간 초과가 발생한다.

범위를 설정해서 특정 범위의 경우만 연산을 진행해야 한다.

코드

제출 코드

import java.io.*;
import java.util.*;

class Main {

    static int N, r, c;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = (int) Math.pow(2, Integer.parseInt(st.nextToken()));
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        func(N, 0, 0, 0);
    }

    static void func(int n, int a, int b, int cnt) throws IOException{
        if(n==2){
            for (int i = a; i <= a+1; i++) {
                for (int j = b; j <= b+1; j++) {
                    if(i==r && j==c){
                        bw.write(String.valueOf(cnt));
                        bw.flush();
                        return;
                    }
                    cnt++;
                }
            }
        } else {
            int divN = n / 2;
            if (    a <= r &&
                    r < a + divN &&
                    b <= c &&
                    c < b + divN)
                func(divN, a, b, cnt);
            else if (a <= r &&
                    r < a + divN &&
                    b + divN <= c &&
                    c < b + N)
                func(divN, a, b + divN, cnt + divN * divN);
            else if (a + divN <= r &&
                    r < a + N &&
                    b <= c &&
                    c < b + divN)
                func(divN, a + divN, b, cnt + divN * divN * 2);
            else
                func(divN, a + divN, b + divN, cnt + divN * divN * 3);
        }
    }
}