[Java] BOJ1074, 백준 - Z

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

1074번: Z

 

개인적으로 분할정복에 약해서 좀 어려웠던 문제이다.

아이디어를 얻어서 문제를 풀었다기보다는, 그림을 그려가며 규칙을 발견해서 이에 맞춘 느낌?

 

이 문제를 N별로 찬찬히 들여다보면 다음과 같은 규칙을 발견할 수 있음

빨>주>노>초 순으로 1>2>3>4

 

1. N=1일 때

또한 왼쪽 위 칸을 기준으로 인덱스는

 

2. N=2일 때

왼쪽 위 영역에서 0,0좌표의 숫자를 기준으로 한다.

 

3. N=3일 때

 

그러면 인덱스를 기준으로 규칙성을 발견할 수 있다.

네 구역으로 나눴을 때 가장 왼쪽 위 칸의 시작은 0에 2^(2*(N-1))이 된다.

 

그리고 빨주노초 칸의 인덱스를 보면

 

빨간색 칸

i : 0~2^(n-1), j: 0~2^(n-1)

 

주황색 칸

i : 0~2^(n-1), j: 2^(n-1)~2^n

 

노랑색 칸

i : 2^(n-1)~2^n, j : 0~2^(n-1)

 

초록색 칸

i : 2^(n-1)~2^n, j: 2^(n-1)~2^n

 

근데 여기서 인덱스가 0미만이거나 2^n이상인 경우는 없기 때문에 인덱스 비교조건은 더 간단하다.

이 규칙을 가지고 쇽쇽 1/4씩 줄어들면 시간복잡도 n만에 풀 수 있다.

 

이 규칙 그대로 코드를 짜면 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		long r = Integer.parseInt(st.nextToken());
		long c = Integer.parseInt(st.nextToken());

		go(r, c, n, 0);

	}

	private static void go(long i, long j, int n, int add) {
		if (n == 1) {
			System.out.println(add + 2 * i + j);
			return;
		}

		int idx = (int) Math.pow(2, n - 1);
		int addnum = (int) Math.pow(2, 2 * (n - 1));
		if (i < idx && j < idx) {
			// 왼쪽위
			go(i, j, n - 1, add);
		} else if (i < idx && j >= idx) {
			// 오른쪽 위
			go(i, j - idx, n - 1, add + addnum);
		} else if (i >= idx && j < idx) {
			// 왼쪽 아래
			go(i - idx, j, n - 1, add + addnum * 2);
		} else if (i >= idx && j >= idx) {
			// 오른쪽 아래
			go(i - idx, j - idx, n - 1, add + addnum * 3);
		}

	}
}

 

보니깐 조건문 부분을 좀 더 줄일 수 있는데,

코드는 더 짧긴 한데 나는 갠적으로 위코드가 좀더 보기좋은 것 같다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		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());

		go(r, c, n, 0);

	}

	private static void go(int i, int j, int n, int add) {
		if (n == 1) {
			System.out.println(add + 2 * i + j);
			return;
		}

		int idx = (int) Math.pow(2, n - 1);
		int iflag = (i >= idx) ? 1 : 0;
		int jflag = (j >= idx) ? 1 : 0;

		go(i - iflag * idx, j - jflag * idx, n - 1, add + (int) Math.pow(2, 2 * (n - 1)) * (iflag * 2 + jflag));
	}
}