[JAVA] 백준 1047번: Z

 

---

문제

• $2^{N}$ x $2^{N}$의 2차원 배열을 Z모양으로 탐색한다.
• N > 1 인 경우, 배열 크기가 $2^{N-1}$ x $2^{N-1}$ 로 4등분 한 후에 재귀적으로 순서대로 방문한다.
• N, r, c가 주어질 때, r행 c열을 몇 번째로 방문하는지 구하는 문제.

 

아이디어

• 매번 배열 크기를 반으로 줄이고, 이를 기준으로 나눈 4분면 중에 (r, c)가 어느 사분면에 위치하는지 파악한다.
• 파악 후, 각 사분면에 해당하는 연산을 수행한 후, 다시 이 과정을 반복한다.
• 더이상 크기를 나눌 수 없는 즉, 크기가 1일때, 우리가 찾는 (r, c) 요소가 나온다.
  • 4 x 4 사이즈의 배열에서 (0, 3) 요소가 몇 번째로 탐색되는지 체크해보자.
  • (0, 3)은 2 x 2 사이즈의 1사분면에 속하므로, 2사분면의 요소 수 만큼 값을 더해준다. (answer += 2 x 2)
  • (0, 3)은 1 x 1 사이즈의 2사분면에 속하므로, 1사분면의 요소 수 만큼 값을 더해준다. (answer += 1 x 1)
  • 그럼 정답은 5가 된다.

(0, 3) 요소를 탐색하는 과정

 

풀이

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

public class Main {
    static int r, c, answer, cnt;
    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());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int size = (int) Math.pow(2, N);

        recur(size, 0, 0);
        System.out.println(answer);
    }
    static void recur(int size, int x, int y) {
        if(size == 1) {
            answer = cnt;
            return;
        }
        // 2사분면에 속할 때
        if(r < x+size/2 && c < y+size/2) {
            recur(size/2, x, y);
        }
        // 1사분면에 속할 때
        else if(r < x+size/2 && c >= y+size/2) {
            cnt += size/2*size/2;
            recur(size/2, x, y+size/2);
        }
        // 3사분면에 속할 때
        else if(r >= x+size/2 && c < y+size/2) {
            cnt += size/2*size/2*2;
            recur(size/2, x+size/2, y);
        }
        // 4사분면에 속할 때
        else {
            cnt += size/2*size/2*3;
            recur(size/2, x+size/2, y+size/2);
        }
    }
}

 

채점 결과

1074번 채점 결과

기타

• 처음에 배열을 사용했다가 메모리 초과가 났고, 두 번째에 z 방향으로 모두 순회한 후 (r, c) 요소를 출력했더니 시간 초과가 났다... 규칙성을 찾는 습관을 들이자.

 

문제 링크

• 1074번: Z (acmicpc.net)