[백준] 1074 백준 (JAVA)

https://www.acmicpc.net/problem/1074

1074번: Z

 

풀이

이 문제는 처음에는 재귀를 이용한 분할 정복 문제이다. 여기서 중요한 점은 n이 조금만 커져도 배열의 크기가 엄청 커진다는 점이다. 그렇기에 우리는 불필요한 위치까지 탐색할 필요가 없다.

여기서 중요한 점은 전체 배열의 크기를 줄인다는것에 있다.

즉 문제에서 주어지는 r, c는 가만히 두되 전체 배열의 크기를 점점 줄여 나가면서 (r,c)가 위치한 사분면에 따라 분할하고 재귀적으로 정복하면 된다. 자세한것은 코드를 보면 이해될것이다. (코드가 그리 길지않기에..)

 

코드

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

class Main {
    public static int count = 0;

    public static void main(String[] args) throws IOException {
        int N, R, C;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int size = (int) Math.pow(2, N);

        find(size, R, C);

        System.out.println(count);
    }

    public static void find(int size, int r, int c) {
        if (size == 1)
            return;

        else if (r < size / 2 && c < size / 2) { //1사분면
            find(size / 2, r, c);
        }
        else if (r < size / 2 && c >= size / 2) { //2사분면
            count += (size * size / 4);
            find(size / 2, r, c - size / 2);
        }
        else if (r >= size / 2 && c < size / 2) { //3사분면
            count += (size * size / 4) * 2;
            find(size / 2, r - size / 2, c);
        }
        else { //4사분면
            count += (size * size / 4) * 3;
            find(size / 2, r - size / 2, c - size / 2);
        }

    }
}