[Epper] 백준 1074번 Z java 자바

문제

https://www.acmicpc.net/problem/1074

1074번: Z

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

풀이

처음에는 재귀로 풀려했는데 최대 범위가 2^15라서 메모리 초과가 발생한다.

따라서 재귀를 사용하지 않고 반복문을 사용하여 풀었는데 그 방법은 다음과 같다.

N=3, 즉 배열의 크기가 8*8일 때를 살펴보자면

8*8일 때 각 사분면의 첫번째 수는 0, 16, 32, 48

4*4일 때 0, 4, 8, 12

2*2일 때 가장 첫번째 수가 0, 1, 2, 3

인 것을 볼 수 있다.

이를 일반화를 한다면

n*n일 때 각 사분면의 첫번째 수는

(n/2) * (n/2) * 0

(n/2) * (n/2) * 1

(n/2) * (n/2) * 2

(n/2) * (n/2) * 3

이 된다.

 

따라서 이를 이용하여 각 사분면에 따라 계산해준다.

 

코드

package Level2;

import java.util.Scanner;
public class BOJ1074_Z {
	
	static int[][]arr;
	static int cnt=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int r=sc.nextInt();
		int c=sc.nextInt();
		
		int size=1;
		for(int i=0;i<N;i++	) {
			size*=2;
		}
		
		int cnt=0;
		int x=0;
		int y=0;
		
		while(size>0) {
			size/=2;
			
			if(r<x+size&&c<y+size) {
				cnt+=size*size*0;
			} else if(r<x+size&&c>=y+size) {
				cnt+=size*size*1;
				y+=size;
			} else if(r>=x+size&&c<y+size) {
				cnt+=size*size*2;
				x+=size;
			} else {
				cnt+=size*size*3;
				x+=size;
				y+=size;
			}
			
			if(size==1) {
				System.out.println(cnt);
				break;
			}
		}
		
	}
	
//  재귀로 풀이(틀린 부분)
//	static void solution(int row, int col, int size) {
//		if(size==2) {
//			arr[row][col]=cnt++;
//			arr[row][col+1]=cnt++;
//			arr[row+1][col]=cnt++;
//			arr[row+1][col+1]=cnt++;
//			
//			return;
//		}
//		
//		int newSize=size/2;
//		solution(row, col, newSize);
//		solution(row, col+newSize, newSize);
//		solution(row+newSize, col, newSize);
//		solution(row+newSize, col+newSize, newSize);
//	}
//	
	
}