[백준] 1074번 Z 자바 (분할정복)

목차

• 문제풀이
  • 시간초과
  • 탐색 범위 좁히기
  • 4각형의 첫번째 값 파악하기
• 제출코드

 

 

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

1074번: Z

 

 

 

문제풀이

시간초과

보드를 반복적으로 4등분하여 Z 모양으로 읽어야한다.

분할정복을 생각해서 풀었지만.. 시간초과가 발생한다.

히히 내 삽질..

 

탐색 범위 좁히기

문제를 다시 살펴보자

61을 찾으려면 굳이 모든 부분을 탐색해야할까?

아니다. 4등분한 우측하단으로 범위를 좁히고

다시 우측하단으로 범위를 좁혀서 Z 탐색하면된다.

 

 

그럼 61(6, 7)이 우측하단에 위치하는 것을 어떻게 찾아내면될까?

N이 8일때 

	X		Y
왼쪽	0~3	위	0~3
오른쪽	4~7	아래	4~7

왼쪽은 X가 0~3까지, 오른쪽은 X가 4~7까지이다.

위는 Y가 0~3까지, 아래는 Y가 4~7까지이다.

 

61의 X인 6은 4~7에 해당하니 오른쪽

61의 Y인 7은 4~7에 해당하니 아래에 해당된다.

=============================================================

N이 4일때

	X		Y
왼쪽	4~5	위	4~5
오른쪽	6~7	아래	6~7

왼쪽은 X가 4~5까지, 오른쪽은 X가 6~7까지이다.

위는 Y가 4~5까지, 아래는 Y가 6~7까지이다.

 

61의 X인 6은 6~7에 해당하니 오른쪽

61의 Y인 7은 6~7에 해당하니 아래에 해당된다.

=============================================================

N이 2일때는 Z 탐색이 가능해진다. Z탐색 하면서는 +1씩 증가할것이고,

(6, 7)을 탐색할 때 count가 61이 되려면

 

N이 2인 탐색을 시작하기 전에 count가 60이 되어있어야한다!!!!

 

 

 

4각형의 첫번째 값 파악하기

count를 알아내려면 쪼개진 범위의 첫번째 값을 파악하면된다.

 

N이 8일때 4등분하면 Half는 4( 8/2 = 4 ), 각 첫번째 시작값은 [0, 16, 32, 48] 이다.

0 = (4 * 4) * 0

16 = (4 * 4) * 1

32 = (4 * 4) * 2

48 = (4 * 4) * 3

....

 

 

N이 4일때 4등분하면 Half는 2( 4/2 = 2 ), 각 첫번째 시작값은 [0, 4, 8, 12, 16, 20, 24, 28....] 이다.

0 = (2 * 2) * 0

4 = (2 * 2) * 1

8 = (2 * 2) * 2

12 = (2 * 2) * 3

....

 

 

규칙도 찾았으니 이제 코드로 작성해보자

 

 

제출코드

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

public class Main {

    static int count  = 0;
    static int findX;
    static int findY;
    static boolean find = false;

    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());
        findY = Integer.parseInt(st.nextToken());       //열⭐⭐⭐
        findX = Integer.parseInt(st.nextToken());       //행⭐⭐⭐
        int size = (int) Math.pow(2, N);
        //===============================
        //입력완료

        partition(0, 0, size);
        System.out.println(count-1);	//-1 ⭐⭐⭐
    }

    private static void partition(int startX, int startY, int size) {
        if(size <= 2){
            findXY(startX, startY);
            return;
        }

        int half = size/2;
        boolean left =          startX <= findX && findX < startX + half;
        boolean right =  startX + half <= findX && findX < startX + size;
        boolean top =           startY <= findY && findY < startY + half;
        boolean bottom = startY + half <= findY && findY < startY + size;


        if(left && top){
            partition(startX, startY, half);
            
        }else if(right && top){
            count = count + ((half * half) * 1);
            partition(startX+half, startY, half);
            
        }else if(left && bottom){
            count = count + ((half * half) * 2);
            partition(startX, startY+half, half);
            
        }else if(right && bottom){
            count = count + ((half * half) * 3);
            partition(startX+half, startY+half, half);
        }

    }


    private static boolean findXY(int startX, int startY){

        //Z 방향으로 확인
        for (int j = startY; j < startY + 2; j++) {     //Y가 먼저
            for (int i = startX; i < startX+2; i++) {
                count++;
                if (i == findX && j == findY) {
                    return true;
                }
            }
        }

        return false;
    }

}