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
풀이
이 문제는 큰 문제를 작은 문제로 나눠서 해결하는 분할 정복 문제이다.
우선 n을 기준으로 4사분면으로 나누어 지는 것을 확인할 수 있다.
n이 0보다 클 때 r과 c가 속한 사분면을 찾은 후 r과 c를 상대위치로 재조정한다.
ex) (r,c) => 4사분면일경우 r - 2^n, c - 2^n
그리고 답에 지나온 사분면의 칸 갯수만큼 더해준다.
이를 n이 0이 될때까지 반복하면 된다.
코드
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();
System.out.println(func(n, r, c, 0));
}
static int func(int n, int r, int c, int ans) {
if (n == 0) {
return ans;
}
int quadrant = find(n, r, c);
int temp = (int) Math.pow(2, n - 1);
int quadrantSize = temp \* temp;
// System.out.println(n + " " + r + " " + c + " " + ans + " " + quadrant);
switch (quadrant) {
case 1:
return func(n - 1, r, c, ans);
// break;
case 2:
return func(n - 1, r, c - temp, ans +quadrantSize);
// break;
case 3:
return func(n - 1, r - temp, c, ans + (2 \* quadrantSize));
// break;
case 4:
return func(n - 1, r - temp, c - temp, ans + (3 \* quadrantSize));
// break;
default:
return -1;
}
}
static int find(int n, int r, int c) {
int xLen = (int)Math.pow(2, n - 1);
int yLen = xLen;
if(r < xLen && c < yLen){
return 1;
} else if (r >= xLen && c < yLen) {
return 3;
} else if (r < xLen && c >= yLen) {
return 2;
} else{
return 4;
}
}
}
'알고리즘' 카테고리의 다른 글
10825 국영수 (0) | 2022.03.25 |
---|---|
2110 공유기 설치 (0) | 2022.03.25 |
2293 동전 1 (0) | 2022.03.25 |
2155 포도주 시식 (0) | 2022.03.25 |
1912 연속합 (0) | 2022.03.25 |