1074번 Z

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

1074번: Z

 

---

문제

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

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

 

예제 입력 1

2 3 1

예제 출력 1

11

 

---

 

구현할 방법

 1) 가장 큰 사각형을 4분할 한뒤, r과 c가 몇 사분면에 해당하는지 탐색

 2) 이 과정에서 r과 c가 속하는 사분면 시작번호 계산

 3) 또 다시 그 사분면을 4분할 하여 r과c가 몇 사분면에 해당하는지 탐색

 4) 이 과정에서 r과 c가 속하는 사분면 시작번호 계산

 5) 분할한 면적이 1*1일때 시작번호 return 하고 종료

 

 

구현 코드

import java.io.*;
import java.util.*;
public class Main {
	static int result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		int width = (int)(Math.pow(2, N));
		divide(width,r,c,0);
		bw.write(result+"");
		bw.flush();
		br.close();
		bw.close();
	}
	public static void divide(int width, int r, int c, int num) {
		int middle = width/2;
		if(middle == 0) {
			result = num;
			return;
		}
		if(r<middle && c<middle) {		//1사분면
			divide(width/2, r, c, num);
		}else if(r<middle && c>=middle) {	//2사분면
			divide(width/2, r, c-middle, num+middle*middle);
		}else if(r>=middle && c<middle) {	//3사분면
			divide(width/2, r-middle, c, num+middle*middle*2);
		}else if(r>=middle && c>=middle){	//4사분면
			divide(width/2, r-middle, c-middle, num+middle*middle*3);
		}
	}

}

 

 

주의사항

해당문제의 시간 제한은 0.5초이기 때문에 이중 배열을 생성하여 모든 값을 넣으려고 하면 시간초과가 발생합니다. 따라서 사분면과, 해당 사분면에 들어설때의 초기값을 파악하면서 분할 해나가는 것이 중요합니다.