BOJ-1074 ) Z

---

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

1074번: Z

 

---

 

길이가 2^N인 사각형에서 1,2,3,4 분면을 결정한다면, 재귀적으로 상황이 반복됨을 알수있다.

즉 좌표의 값은, 1사분면일경우 그대로, 2사분면인경우 y,x-2^(n-1)

3사분면인경우 y-2^(n-1),x 4사분면인경우y-2^(n-1),x-2^(n-1)으로 반복된다.

 

또한 사분면에 찍히는 순서의 경우 0,0의 기준에서 2^(2*N-2) * ( 사분면의 수 -1 ) 만큼 

보정치를 더해준다.

 

만약 그냥 구현으로 생각해서 사분면에 찍히는 수를 하나하나 계산하면, 시간초과를 받게된다.. 

---

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

public class BOJ_1074 {
	public static int answer =0;
	public static void main(String[] args) throws IOException  {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		recursion(r, c, 0, n);
		System.out.println(answer);
	}
	private static void recursion(int y, int x, int score, int N) {
		if(N==1) {
			if(y==0&&x==0)answer =score;
			else if(y==0&&x==1)answer =score+1;
			else if(y==1&&x==0)answer =score+2;
			else if(y==1&&x==1)answer =score+3;
			return;
		}
		int len = (int) Math.pow(2, N-1);
		if(y<len&&x<len) {
			recursion(y, x, score, N-1);
		} else if(y<len&&x>=len) {
			recursion(y, x-len, score+(int)Math.pow(2, 2*N-2), N-1);
		} else if(y>=len&&x<len) {
			recursion(y-len,x, score+(int)Math.pow(2, 2*N-2)*2, N-1);
		} else {
			recursion(y-len,x-len, score+(int)Math.pow(2, 2*N-2)*3, N-1);
		}
		
		
	}

}

 

---