Z (백준 1074번) [JAVA]

문제

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

1074번: Z

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5초	512 MB	23026	7419	5468	38.515%

한수는 크기가 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

 

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int N;
	static int r;
	static int c;
	static int ans = 0;
	public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	public static void main(String[] args) throws NumberFormatException, IOException {
		  String lines = br.readLine();
	      String[] spl  = lines.split(" ");
	      N=Integer.parseInt(spl[0]);
	      r=Integer.parseInt(spl[1]);
	      c=Integer.parseInt(spl[2]);  
	      System.out.println(solveZ(N,r,c));
	}
	
	public static int solveZ(int N,int r,int c) {
		N--;
		if(N < 0) {
			return ans;
		}
		int x = Zal(N,r); 
		int y = Zal(N,c);
		r = r - (int)Math.pow(2, N)*x; 
		c = c - (int)Math.pow(2, N)*y;
		ans = (2*x+y)*(int)Math.pow(2, 2*N) + solveZ(N,r,c);
		return ans;
	}
	
	
	public static int Zal(int N, int r) {
		int x = 0;	
		while(x >= 0) {
			x++;
			r = r - (int)Math.pow(2, N)*x;
			if(r < 0) { 
				x--;
				break;
			}
		}
		return x;
	}
} 

 

결과