[BOJ 1074] Z (Java)

문제

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

1074번: Z

 

풀이

분할정복 문제이다. 

 

유사 문제 

2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java)

2021.11.23 - [Problem Solving/Programmers] - [프로그래머스] 쿼드 압축 후 개수 세기 (Java)

2021.11.17 - [Problem Solving/BOJ] - [BOJ 1992] 쿼드트리 (Java)

 

* 핵심 포인트

해당 문제는 전수로 분할정복을 할 경우 시간 초과가 발생한다. 

주어진 범위를 가지고 (R, C) 좌표가 어떤 사분면에 속해 있는지 판단하여, 속하지 않은 사분면의 탐색을 생략해야 한다.

속한 사분면을 탐색하기 전에 순서가 생략된 사분면의 칸의 개수를 먼저 더해주고 탐색을 진행한다.

(사분면의 순서는 문제에 나와있는 순서로 정하여 풀었다. 수학적 지식X)

 

소스코드

package divideconquer;

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

public class BOJ1074 {

    static int N, R, C, answer;
    public static void main(String[] args) throws Exception {
        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());
        // 2^N * 2^N 행렬

        divide(0, 0, (int)Math.pow(2, N));
    }

    public static int[][] order = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
    public static void divide(int x, int y, int n){
        if(n > 2){
            int quarterSpace = getQuarterSpace(x, y, n);
            if(quarterSpace == 1){
                divide(x, y, n/2); // up left 1
            } else if(quarterSpace == 2){
                answer += Math.pow(n, 2)*((double)1/4);
                divide(x, y+n/2, n/2); // up right 2
            }else if(quarterSpace == 3){
                answer += Math.pow(n, 2)*((double)2/4);
                divide(x+n/2, y, n/2); // down left 3
            } else {
                answer += Math.pow(n, 2)*((double)3/4);
                divide(x+n/2, y+n/2, n/2); // down right 4
            }
        } else {
//            System.out.println(x + ", " + y);
            for(int[] o : order){
                int r = x + o[0];
                int c = y + o[1];
                if(r == R && c == C){
                    System.out.println(answer);
                    System.exit(0);
                }
                answer++;
            }
        }
    }

    public static int getQuarterSpace(int x, int y, int n){
        int rs = 0;
        if(R >= x && R < x+n/2 && C >= y && C < y+n/2) rs = 1;
        if(R >= x && R < x+n/2 && C >= y+n/2 && C < y+n/2+n/2) rs = 2;
        if(R >= x+n/2 && R < x+n/2+n/2 && C >= y && C < y+n/2) rs = 3;
        if(R >= x+n/2 && R < x+n/2+n/2 && C >= y+n/2 && C < y+n/2+n/2) rs = 4;
        return rs;
    }
}