[알고리즘] 백준 > #1074. Z

문제링크

백준 #1074. Z

풀이방법

분할정복 문제다! 사각형의 크기가 2 2가 될때까지 계속 사등분하면 된다. 2 2가 되었을 때 해당 사각형의 (0, 0) (0, 1), (1, 0), (1, 1)를 r, c와 비교하고 count를 늘린다. 단, 모든 케이스에 대해 진행하면 시간초과가 발생하기 때문에 가지치기가 필요하다! 가지치기는 isIncludeTarget() 메소드로 구현했는데, 그냥 size, y, x좌표가 주어졌을 때 그 사각형 안에 r, c가 속하는지 확인만 하면된다~~ 쉬운문제였다!

코드

import java.util.*;
public class BOJ1074 {

    static private int count = -1;

    static private int r;
    static private int c;

    static private int[] nextY = {0, 0, 1, 1};
    static private int[] nextX = {0, 1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        r = sc.nextInt();
        c = sc.nextInt();

        findTarget(n, 0, 0);

        System.out.print(count);
    }

    private static boolean findTarget(int power, int startY, int startX) {
        if (power > 1) {
            int nextSize= (int) Math.pow(2, power - 1);
            for (int i = 0; i < 4; i++) {
                int nextStartY = startY + nextY[i] * nextSize;
                int nextStartX = startX + nextX[i] * nextSize;

                if (isIncludeTarget(nextSize, nextStartY, nextStartX)) {
                    if (findTarget(power - 1, nextStartY, nextStartX)) return true;
                } else {
                    count += (nextSize * nextSize);
                }
            }
        }
        else {
            for (int i = 0; i < 4; i++) {
                int zY = startY + nextY[i];
                int zX = startX + nextX[i];

                count++;

                if ((zY == r) && (zX == c)) return true;
            }
        }

        return false;
    }

    private static boolean isIncludeTarget(int size, int startY, int startX) {
        return ((startY <= r) && (r < (startY + size)) && (startX <= c) && (c < (startX + size)));
    }
}