[백준 온라인 저지] 1074. Z

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

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

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

N=3일 때 방문 순서

 

1. 입력

- 첫째 줄에 정수 N, r, c가 주어진다.

- 1 ≤ N ≤ 15

- 0 ≤ r, c < 2^N

 

2. 출력

- r행 c열을 몇 번째로 방문했는지 출력한다.

 

3. 예제

 

4. 코드

1) 첫 코드 - 맞긴 하나 시간초과

import java.util.*;
import java.io.*;
class Main {
    static int R, C;
    static boolean found = false;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(token.nextToken());
        R = Integer.valueOf(token.nextToken()); C = Integer.valueOf(token.nextToken());
        find((int)Math.pow(2,N), 0, 0);
        System.out.print(ans);
    }
    
    static void find(int n, int r, int c){
        if(n==2){
            if(r==R && c==C) { found = true; return; }
            ans++;
            if(r==R && c+1==C) { found = true; return; }
            ans++;
            if(r+1==R && c==C) { found = true; return; }
            ans++;
            if(r+1==R && c+1==C) { found = true; return; }
            ans++;
            return;
        }
        if(!found) find(n/2, r, c);
        if(!found) find(n/2, r, c+n/2);
        if(!found) find(n/2, r+n/2, c);
        if(!found) find(n/2, r+n/2, c+n/2);
    }
}

 

2) 4개의 사분면 중 1개만 택해서 계산하게끔 바꾼 코드

import java.util.*;
import java.io.*;
class Main {
    static int R, C;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(token.nextToken());
        R = Integer.valueOf(token.nextToken()); C = Integer.valueOf(token.nextToken());
        find((int)Math.pow(2,N), 0, 0);
        System.out.print(ans);
    }
    
    static void find(int n, int r, int c){
        if(n==2){
            if(r==R && c==C) return;
            ans++;
            if(r==R && c+1==C) return;
            ans++;
            if(r+1==R && c==C) return;
            ans++;
            if(r+1==R && c+1==C) return;
            ans++;
            return;
        }
        if(R<r+n/2){
            if(C<c+n/2) find(n/2, r, c); // 2사분면
            else {
                ans += n*n/4;
                find(n/2, r, c+n/2); // 1사분면
            }
        } else{
            ans += n/2*n;
            if(C<c+n/2) find(n/2, r+n/2, c); // 3사분면
            else {
                ans += n/4*n;
                find(n/2, r+n/2, c+n/2); // 4사분면
            }
        }
    }
}

- 14212KB, 128ms