[백준/java] 1074.Z

문제 링크 - https://www.acmicpc.net/problem/1074

🌱 문제

🌱 풀이

• 분할정복을 이용하여 풀었다.
• 처음에 풀이한 코드인데 계속 메모리 초과가 났다. (r,c)에 도달했을 때 종료조건을 안걸어줘서 메모리 초과가 난것같아서 해당 부분을 추가해주었다.

if(half==1) {
			
			arr[r_][c_]=num;
			arr[r_][c_+1]=num+1;
			arr[r_+1][c_]=num+2;
			arr[r_+1][c_+1]=num+3;
			if(arr[r][c]!=0) {
				System.out.println(arr[r][c]);
				System.exit(0); // 메인함수 종료 
			}
			
			return;
		}

• 그럼에도 메모리 초과가 나서 아직 이유를 잘 모르겠다. 두번째 풀이방법으로 풀었더니 메모리 초과가 안나서 다시 생각해보니 arr= new int[n1][n1]; 여기에서 메모리 초과가 난것같다. 최대 2^15 x 2^15 크기의 배열이 만들어지기 때문이다.

• 처음에 생각한 풀이

package Sep_week04;

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

public class boj_1074 {
	
	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 n1=(int)Math.pow(2, n);
		arr= new int[n1][n1];
		
		func(0,0,n1/2,0);
		
	}
	public static void func(int r_,int c_, int half,int num) { //half: 현재 보고있는 정사각형 한변의 길이의 반 
		if(half==1) {
			
			arr[r_][c_]=num;
			arr[r_][c_+1]=num+1;
			arr[r_+1][c_]=num+2;
			arr[r_+1][c_+1]=num+3;
			
			return;
		}
		
		
		func(r_,c_,half/2,num);
		func(r_,c_+half,half/2,num+half*half);
		func(r_+half,c_,half/2,num+2*half*half);
		func(r_+half, c_+half, half/2,num+3*half*half);
		
	}

}

🌱 코드

package Sep_week04;

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


//1074.Z
public class boj_1074 {
	
	static int N,R,C;
	static int answer;
	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 n1=(int)Math.pow(2, N);
		
		func(0,0,n1);	
		System.out.println(answer);
		
	
		
	}
	public static void func(int r, int c, int size) {
		if(size==1) //한변의 길이가 1이되면 리턴 
			return;
		
		int newSize= size/2;  //재귀마다 한변의 길이 반토막 
		if(R<r+newSize && C<c+newSize) { //4등분 했을때, (r,c)좌표의 위치가 1사분면일 경우 
			// answer  변화 없음
			func(r,c,newSize);
		}else if(R<r+newSize && C>=c+newSize) { //2사분면일 경우 
			answer+= newSize*newSize;
			func(r,c+newSize, newSize);
			
		}else if(R>=r+newSize && C<c+newSize) { //3사분면일 경우
			answer+=newSize*newSize*2;
			func(r+newSize, c,newSize);
		}else { //4사분면일 경우
			answer+=newSize*newSize*3;
			func(r+newSize, c+newSize, newSize);
		}
	}
	

}