BOJ_Z_1074(Java)

문제 링크

성능 요약

메모리: 14284 KB, 시간: 104 ms

분류

분할 정복, 재귀

제출 일자

2024년 12월 13일 16:15:42

문제 설명

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

풀이

• 느낀점
  문제에 ‘재귀적으로 방문’이라는 말에서 힌트를 얻었다. 깨닫기 전까지는 어려운 문제라고 생각했는데, 고민을 좀 해보니 비교적 간단한 문제였다.

• 설계 시간: 40분

  💡 설계 아이디어

  • 주어진 r과 c가 4등분한 칸의 크기보다 큰지 작은지를 확인하여 몇번째 칸에 해당하는지 이전 순서의 개수를 더한다.
  • 이전 순서의 칸을 계산했다면 n을 하나 더 줄여 범위를 좁힌 후에 같은 방식으로 재귀한다.
  • 4등분한 칸의 크기가 1보다 작으면 더이상 구할 수 없으므로, 재귀를 return한다.

코드

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Date: 2024.12.03
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] inputs = br.readLine().split(" ");
		int N = Integer.parseInt(inputs[0]);
		long r = Long.parseLong(inputs[1]);
		long c = Long.parseLong(inputs[2]);

		long answer = findOrder(N-1, r, c);
		bw.write(String.valueOf(answer));

		bw.flush();
		bw.close();
		br.close();
	}

	public static long findOrder(int n, long r, long c) {
		if (n < 0) return 0;

		long count = 0;
		long length = (long) Math.pow(2, n);
		if (r + 1 > length) {
			count += (length * length * 2);
			r -= length;
		}
		if (c + 1 > length) {
			count += (length * length);
			c -= length;
		}
		count += findOrder(n - 1, r, c);

		return count;
	}
}