728x90
성능 요약
메모리: 12912 KB, 시간: 112 ms
분류
분할 정복(divide_and_conquer), 재귀(recursion)
문제 설명
한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.
분할 정복으로 풀면 되는 문제다. 처음에는 배열을 선언해서 cnt를 더하였는데, 이러면 입력의 크기가 커질 때 메모리가 부족하다.
그래서 배열을 선언하지 않고 cnt를 증가시키면서 하였는데, 1씩 증가하다 보니 시간초과가 난다.
배열 전체는 4등분이 가능하니까 r과 c가 위치한 사분면에 따라 위치하지 않은 사분면은 cnt가 배열의 크기만큼 증가한다.
이를 활용해서 함수를 구현하였다.
package Silver.s1;
import java.util.Scanner;
public class BOJ_1074_Z {
static int cnt;
static int ans;
static int[][] map;
static int row, col;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
row = sc.nextInt();
col = sc.nextInt();
findZ(0, 0, (int) (Math.pow(2, N)));
System.out.println(ans);
}
static void findZ(int r, int c, int size) {
if (r == row && c == col && size == 1) {
ans = cnt;
return;
}
if (size == 1) {
cnt++;
return;
} else {
// 4개중에 r, c가 위치한 곳 찾기
int dis = size / 2;
if (row < r + dis && col < c + dis) // 위치가 1
findZ(r, c, dis);
cnt += dis * dis;
if (row < r + dis && col >= c + dis) // 2
findZ(r, c + dis, dis);
cnt += dis * dis;
if (row >= r + dis && col < c + dis) // 3
findZ(r + dis, c, dis);
cnt += dis * dis;
if (row >= r + dis && col >= c + dis)
findZ(r + dis, c + dis, dis);
cnt += dis * dis;
}
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 17070 - 파이프 옮기기 1 (자바/Java) (0) | 2022.09.20 |
---|---|
[백준] 10830 - 행렬제곱 (자바/Java) (1) | 2022.09.20 |
[백준] 10972 - 다음 순열 (자바/Java) (0) | 2022.09.20 |
[백준] 2448 별 찍기 - 11 (자바/Java) 재귀, 분할정복 (0) | 2022.09.19 |
[벡준] 5014 - 스타트링크 (자바/Java) (0) | 2022.09.15 |