[Algorithm] 백준_Z_1074번 (JAVA) 분할정복

📝문제

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

Z 1074번

티어 : 골드 5

💡풀이

문제 유형

분할정복

 

걸린 시간

40분? 50분?

 

시간 복잡도

O(N)

 

풀이 방법 도출

1. r과 c가 현재 사이즈를 사등분 후 왼쪽 위인지, 오른쪽 위인지, 왼쪽 아래인지, 오른쪽 아래인지 판단하는 문제다.
2. 우선 size = 2^N으로 정의 가는하고, 이를 사등분하려면 newSize = size/2가 된다.
3. 그럼 이때 (0,0)을 기준으로 0 + newSize, 0 + newSize와 r,c를 비교 검사해 위치를 구한다.
4. 이후 왼쪽 위인 경우는 count를 그대로, 오른쪽 위인 경우 count에 newSize*newSize를 더해준다. 왼쪽 아래인 경우는 newSize*newSize*2,  오른쪽 아래는 newSize*newSize*3을 더해준다. ( 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서이므로!)
5. 그리고 재귀로 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸의 가장 왼쪽 위칸을 x,y로 넘겨준다.
6. 그럼 다시 새로운 사이즈와 새로운 위치로 카운트를 더해주면 된다.

import java.util.*;
import java.io.*;
class Main{
    static int r, c;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        int size = (int) Math.pow(2,N);
        recursive(size, 0, 0);

        System.out.println(count);
    }
    public static void recursive(int size, int x, int y){
        if(size == 1) return;
        int newSize = size/2;

        //왼쪽 위
        if(r < x + newSize && c < y + newSize){
            recursive(newSize, x, y);
        }

        //오른쪽 위
        if(r < x + newSize && c >= y + newSize){
            count += newSize * newSize;
            recursive(newSize, x, y+ newSize);
        }

        //왼쪽 아래
        if(r >= x + newSize && c < y + newSize){
            count += newSize * newSize * 2;
            recursive(newSize, x+newSize, y);
        }

        //오른쪽 아래
        if(r >= x + newSize && c >= y + newSize){
            count += newSize * newSize * 3;
            recursive(newSize, x+newSize, y+newSize);
        }
    }
}

 

🤔Review

분할정복이 알고리즘 중 젤 어려운 알고리즘같아