[BOJ] 1074 Z

Z

풀이

• 2^N*2^N 2차원 배열을 Z모양으로 탐색.
  
• N이 주어졌을 때, r행 c열을 몇번째로 방문하는지 출력.
• 앞서 풀었던 쿼드트리, 종이의 개수랑 똑같이 풀었는데 시간 초과 났다.
• 핵심은 4등분을 하면서 r행 c열이 1,2,3,4사분면 중 어디에 있는지를 파악하며 그 부분만 패면 된다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int N,r,c;
    static int[][] map;
    static int cnt = 0;
    static int answer = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int N = (int)Math.pow(2,m);
        cur(N,0,0);
    }
    private static void cur(int n,int i, int j){
        //크기가 1이 되면
        if(n==1){
            System.out.println(answer);
            return;
        }
        int newSize = n/2;
        if(r<i+newSize && c<j+newSize){
            //1사분면
            cur(newSize,i,j);
        }
        //2사분면
        if(r<i+newSize && c>=j+newSize){
            answer+=(n*n)/4;
            cur(newSize,i,j+newSize);
        }
        //3사분면
        if(r>=i+newSize && c<j+newSize){
            answer+=((n*n)/4)*2;
            cur(newSize,i+newSize,j);
        }
        if(r>=i+newSize && c>=j+newSize){
            answer+=((n*n)/4)*3;
            cur(newSize,i+newSize,j+newSize);
        }
    }
}

• 여기서 각 사분면에 answer 구하는 방식이 처음에 이해가 안갔는데, 위 사진에서 4등분했을 때 0,16,32,48이 각 사분면의 시작점이다. 여기서 공식을 구해낸 것. 2사분면이면 (8*8)/4 = 16, 3사분면이면 ((8*8)/4)*2 ...
• 그러다가 r행 c열을 구하게 되는 곳은 size가 1인 곳을 만났을 때다. 그래서 if(n==1) 에서 answer를 출력하는 것!

• 시간초과를 해결하지 못해서 풀이를 봤던 문제다. 분할 정복 어려워. . .🤯