[백준] 1074번 Z

[백준] 1074번 Z

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

문제

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

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

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

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

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

풀이

이 문제는 딱 봐도 재귀적인 문제고, 분할정복 문제이다. 2차원 배열을 좌표평면처럼 생각하면, 각각이 몇 사분면에 속하는지에 따라 탐색순서가 결정됨을 알 수 있다.

N = 1인 경우를 보면

1사분면일 때 0, 2사분면일때 1, 3사분면일때 2, 4사분면일때 3임을 알 수 있다.

N = 2인 경우를 보면

각 사분면에 해당되는 칸이 4개씩 존재한다. 또한, 그 4개의 칸을 좌표평면으로 보고 4개의 칸이 또 몇 사분면에 위치하는지에 따라 순서가 결정된다.

예컨데 1행 1열은 순서대로 1사분면, 4사분면이라 (1-1)*4 + (4-1) = 3이 되고, 3행 2열의 경우 4사분면, 3사분면이라 (4-1) * 4 + (3-1) = 14가 된다. 즉, r 행 c열이 순서대로 몇사분면에 해당되는지 적어둔 수열을 A라 하면 다음 수식이 성립한다.

즉, 주어진 n, r, c 을 사분면정보가 담긴 배열로 변환하면, O(n) 안에 문제를 풀 수 있다. 이때 N이 최대 15이므로, 사실상 상수시간에 문제를 풀 수 있게 된다.

여기까지 하고 남은건 사분면정보를구하는 일뿐인데 사분면정보를 구하는것이 생각보다 좀 까다로웠다. 우선, 좌표평면으로 볼 영역의 양 끝 지점을 알아야 한다. n, r, c rk 3, 5, 3 으로 입력된 경우를 예로들면

이 그림에서 노란색 원은 첫번째 사분면 정보를 구할때 사용되는 좌 우측 끝을 표시한 것이고, 노란색 사각형은 이때의 사분면 판단기준이 되는 기준점을 표시한 것이다. 초록색 원은 두번째 사분면 정보를 구할 때 사용되는 좌 우측끝을 표시한 것이고 초록색 사각형은 이때의 기준점을 표시한 것이다. 파란색 원은 r행 c열 을 표시한 것이다.

사분면 정보가 무었인지에 따라, 다음번 사분면정보를 구할때 사용되는 기준점을 정하는 방법이 달라진다. 위 예시에서 첫번째 사분면 정보가 2 사분면 일 때, 죄측 끝의 열은 이전 사분면기준점의 열과 같고, 행은 이전 사분면기준점의 행 - (이전 사분면의 각 사분면의 행길이)가 된다. 우측끝은 좌측끝이 결정되었고, 길이가 정해지니 자동으로 구해진다.

이와같이 이전의 사분면정보가 무었인지에 따라 다음 사분면기준점을 정하는 방법 4가지를 모두 구했고, 이를 코드로 옮겨 보면 아래와 같다.

import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int r = sc.nextInt(); int c = sc.nextInt(); int[] positions = new int[n]; int nback = n; positions= getPosition(n, r, c); int ret = 0; for(int i=0;i=1;i--) { if(r=piviotC) { position[n-i]=2; leftC = piviotC; leftR = piviotR - (int)Math.pow(2, i-1); rightR = leftR + (int)Math.pow(2, i-1)-1; rightC = leftC + (int)Math.pow(2, i-1)-1; }else if(r>=piviotR && c

from http://blog.robinjoon.space/52 by ccl(S) rewrite - 2021-09-26 05:02:10