[백준/1074] 파티 (실버 1) JAVA

package task.easy.z1074;

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int r;
    static int c;
    static int count = 0;
    static int[] dr;
    static int[] dc;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

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

        // dxdy 정의
        dr = new int[] {0, 0, 1, 1};
        dc = new int[] {0, 1, 0, 1};

        zProcess(N,0, 0);

        System.out.println(result);
    }

    public static void zProcess(int level, int startRow, int startCol) {
        if (result > 0) {
            return;
        }
        if (level == 1) {
            for (int i = 0; i < 4; i++) {
                if (startRow+dr[i] == r && startCol+dc[i] == c) {
                    result = count;
                    return;
                }
                count++;
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int posDivided = (int) Math.pow(2, level - 1);
                if (dr[i]*posDivided+startRow <= r
                        && dr[i]*posDivided+startRow + Math.pow(2, level-1) > r
                        && dc[i]*posDivided+startCol <= c
                        && dc[i]*posDivided+startCol + Math.pow(2, level-1) > c
                ) {
                    zProcess(level-1, dr[i]*posDivided+startRow, dc[i]*posDivided+startCol);
                } else {
                    count += (int) ((int) Math.pow(2, level-1) * Math.pow(2, level-1));
                }
            }

        }
    }

}

• 시간초과 : 최대 크기 2^15 x 2^15의 2차원 배열이므로 모두 계산할 경우 시간초과가 발생한다. target Row, Col을 활용하여 계산하지 않고 넘어가는 방법 도출 필요
• 메모리초과 : 2차원 배열을 실제로 사용하면 안된다. 2^15x2^15 2차원 배열의 메모리는 대략 4GB를 가진다. 32768 x 32768 x 4 바이트(int) = 4294967296 바이트 = 약 4GB
• n=1일때는 2x2, n=2일때는 4x4 n=3일때는 8x8이다. 어떤 크기를 가지던 target row, col 위치가 주어졌을 때 가장 큰 n의 정사각형 모양에서 1,2,3,4분면 중 하나에 위치한다. 그럼 나머지는 내부 계산을 하지 않을 수 있다.

Z방향으로 서치를 진행하므로 2사분면 1사분면 3사분면 4사분면 순서로 진행한다. 만약 해당 사분면내부에 r,c가 존재하지 않는 다면 해당 사분면의 크기를 count에 누적시킨다.

만약 r,c가 존재하는 사분면일 경우 해당 사분면에 대하여 다시 zProcess를 돌린다. 사분면안에서 다시 나뉜 2,1,3,4 사분면에 대해서 이전과 동일한 로직이 작동될 것이다. 또 다시 3가지의 사분면은 계산활동이 거의 무시된다.

이런식으로 빠르게 봐도 될 영역은 한번에 계산하고, 주의깊게 봐야할 영역만 재귀함수를 켜주는 식으로 진행한다.