백준 1074번 메모리 초과 (java)

"종이접기" 문제인 줄 알았다.
종이접기로 풀어도된다.
하지만 메모리 초과가 발생한다.

한가지 생각해보면 종이접기는 2차원 행렬에 대한 값들이 주어진다.
그 값들을 하나하나 점검하면서 검사해야하기 때문에 2차원 배열을 선언해주는 것이 맞다.

그러나 이 문제는 그냥 해당 범위가 어디에 속하는지만 알아도 되는 문제이기 때문에 2차원 배열에 대한 자료를 주지 않았다.
따라서 내가 굳이굳이 종이접기로 풀겠다는 고집으로 2차원 배열을 생성한다면 메모리 초과가 발생한다.

그래서 처음에 시도한 아래의 방법은 정답은 나오나 메모리 초과가 발생한다.

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


public class Main{

    static int[][] arr;

    static int cnt=-1;
    static int result =0;

    static void partition(int row, int col, int size){
        if(size==2){
            for(int i=row;i<row+size;i++){
                for(int j=col;j<col+size;j++){
                    cnt++;
                    if(arr[i][j]==1)
                        result=cnt;

                }
            }

        }else{
            int SIZE = size/2;

            partition(row,col,SIZE);
            partition(row,col+SIZE,SIZE);
            partition(row+SIZE,col,SIZE);
            partition(row+SIZE,col+SIZE,SIZE);

        }


    }

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");


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


        arr = new int[(int)Math.pow(2,N)][(int)Math.pow(2,N)];
        arr[r][c]=1;

        partition(0,0,(int)Math.pow(2,N));

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();

    }



}

따라서 이 방법이 아닌 배열을 선언하지 않고 풀 수 있는 풀이를 고안해야 한다.

먼저 접근법은 이렇다.
1. 구하고자 하는 r과 c의 위치가 어디인지에 따라 종이의 사이즈를 줄여나간다.
2. 따라서 r과 c의 위치는 변한다. 만약 8x8 사이즈의 종이에서 4x4사이즈의 종이로 아래와 같이 변한하다면 r과 c도 그만큼 빼줘야 한다. 사이즈의 1/2만큼 빼줘야 한다.
3. 또한 cnt의 경우도 r이 사이즈의 1/2보다 크거나 같으면 위에를 셋다 치고 더해줘야 한다. 그래서 반절값이 추가된다.
4. c가 사이즈의 1/2보다 크거나 같다면 1/4를 셋다 치고 더해줘야 한다.
5. 따라서 사이즈가 1이 되었을 때 내가 구하길 원했던 그 지점에 도달한다.

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


public class Main{
    
    static int cnt=-1;
    static int r;
    static int c;
    
    static void partition(int row, int col, int size){
            if(size==1) {
                cnt++;
                return;
            }

            if(size/2<=r){
                row= row+size/2;
                cnt+=size*size/2;
                r=r-size/2;
            }
            if(size/2<=c){
                col = col+size/2;
                cnt+=size*size/4;
                c = c-size/2;
            }
            partition(row,col,size/2);

        }


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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);

        partition(0,0,size);

        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
        br.close();

    }



}

여러번 시도 끝에 맞았다.

답은 도달했는데 사용도 안하면서 계속 arr[][]를 남겨놓는 바람에 너무 고생했다.