백준 1074번 Z JAVA

링크텍스트

설명

처음에는 배열을 사용해서 풀었다. 하지만 배열 크기가 N=15일 경우 배열의 크기가
32768×32768라서 메모리 사용량이 너무 커서 메모리 초과가 뜬다.

코드

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

public class Main {

    static int n, r, c;
    static int[][] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int size = 1 << n;

        find(r, c, size);

    }
    static void find(int r, int c, int size) {
        if (size == 1) { 
            System.out.println(count);
            return;
        }
        int half = size / 2;

        if(r < half && c < half) {
			find(r,c,half);
		}
        else if (r < half && c >= half) {
            count += half * half;
            find(r, c - half, half);
        }
        else if (r >= half && c < half) {
            count += half * half * 2;
            find(r - half, c, half);
        }
		else {
            count += half * half * 3;
            find(r - half, c - half, half);
		}
    }
}

메모리 초과 코드

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

public class Main {
    static int n, r, c;
    static int[][] arr;

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

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

        int size = 2*(1 << (n-1)); 
        arr = new int[size][size];

        fill(0, 0, size, 0);

        System.out.println(arr[r][c]);
    }

    static void fill(int x, int y, int size, int order) {
        if (size == 1) { 
            arr[x][y] = order;
            return;
        }

        int half = size / 2;
        int area = half * half;

        fill(x, y, half, order); 
        fill(x, y + half, half, order + area);
        fill(x + half, y, half, order + 2 * area);
        fill(x + half, y + half, half, order + 3 * area);
    }
}

참고 글

https://comain.tistory.com/282
https://wiselog.tistory.com/133