[Java] 백준 1074 : Z

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

1074번: Z

---

 

 2의 N제곱 사이즈의 배열에서 (r,c)을 몇번째로 방문했는지 묻는 문제이다.

 

 1. (r,c)의 위치를 구분했다.

z모양으로 움직이는 순서대로 왼쪽 위/ 오른쪽 위/왼쪽 아래/ 오른쪽아래 어디에 있는지 찾는다. 

 

2. 해당하는 위치에서 가장 앞에 있는 위치의 순서값을 cnt에 합한다. 

여기서 가장 앞에 위치한 것은 각 0, 4,8,12를 의미한다. 

 

3. 이 방법을 반복해서 작동하도록 재귀하여 함수를 호출한다. 

단, 호출해 줄때 r과 c의 위치를 (0,0)에서 시작한 것처럼 호출한다. 

예를 들어 위 그림에서 4의 위치는 (0,2)이었던 것을 호출할 때는 (0,0)으로 만들어 주는 것이다. 

각각을 또 다시 나누었을 때 위치를 파악하기 위함이다.

 

---

import java.util.*;


public class Main {

	static int N,r,c,cnt=0;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		r = sc.nextInt();
		c = sc.nextInt();
		
		find(r,c,(int)Math.pow(2, N));
		System.out.println(cnt);
		
	
	}// main()
	
	static void find(int x,int y, int size) {
		if(size==1)
			return;
		
		if(x<size/2&&y<size/2) {	//왼쪽 위
			find(x,y,size/2);
		}else if(x<size/2&&size/2<=y) {	//오른쪽 위
			cnt+=(size*size/4);
			find(x,y-size/2,size/2);
		}else if(x>=size/2&&size/2>y) { //왼쪽 아래
			cnt+=(size*size/4)*2;
			find(x-size/2,y,size/2);
		}else {						//오른쪽 아래
			cnt+=(size*size/4)*3;
			find(x-size/2,y-size/2,size/2);
			
		}
			
	}
	
}// class Main