[1074번]Z

네이버 웹툰 3번문제의 달팽이가 생각난다. 물론 다른 문제이긴 하지만, 이런 문제를 잘 풀지 못하는 것 같기에 풀어보려 한다.

(역시나 한시간 걸렸다.)

이 문제는 silver1 문제다

- 1074번: Z

Z 모양으로 탐색하려 한다. 배열의 크기는 2 ^ Nx 2^N 이다.

N >1 이라면, 배열을 2^(N-1) x 2^(N-1) 로 2^N 등분 한 후, 재귀적으로 순서대로 방문한다.

• 문제에서 구하고자 하는 것 : N이 주어졌을 때, r행 c열을 몇 번 째로 방문하는지 출력

풀이 생각

• 먼저 몇 번째 칸에 속해있는지를 찾아야 한다.

  • 재귀적으로 순서를 찾아야 한다.

  • 4등분씩 해 나가기 때문에, 각 각에서 몇 번째 칸에 속해있는지 찾아야 한다. 맨 마지막에 Z순으로 2x2에서 돌 때 몇 번째에 방문하게 되는 것인지만 구하면 된다.

    

    N =3 이고, r = 5, c = 5 . 4등분한 사각형을 Z로 방문한다 생각했을 때 몇 번 째 칸에 속했는지를 먼저 알아야 한다.

  • 첫 번째 호출

    • → 2^3 / 2 = 4
    • r≥ 4 && c≥4 → 네 번째 칸에 속함. → 2^2 x 2^2 x 3 개가 앞서 있다.

  • 두 번째 호출

    • → 2^2 / 2 = 2
    • 4+2 = 6
      • 첫 번 째 칸은 (4,4) 에서 시작한다.
    • r<6 && c<6 → 첫 번째 칸에 속함.
    • if, r<6 && c≥6 → 두 번째 칸에 속함
    • if, r≥6 && c<6 → 세 번째 칸에 속함.
    • if, r≥6 && c≥6 → 네 번째 칸에 속함.

즉, 아래와 같이 풀면 될 것 같다.

• 시작점 (0,0)임. = (preR, preC)
  • len = 2 ^(N-1) 으로 시작하여 len 이 2 보다 클 때 까지만 계속한다.
    • 즉 마지막에 while문을 나와서 2x2 칸 안에서 몇 번째 위치인지를 계산하도록 한다.
  • preR + ( 2^N x 2^N / 2 → 2 ^ (N-1) ) 기준으로.. 찾으려는 R 이 그 값 미만인지 이상인지 + preC + ( 2^N x 2^N / 2 → 2 ^ (N-1) ) 기준으로.. 찾으려는 C 가 그 값 미만인지, 이상인지를 기준으로 몇 번 째 칸인지 알 수 있어진다.
  • 몇 번째 칸인지 알게 된다면,
  • 이제는, 시작점은
    • 첫 번째 칸 : ( preR, preC)
    • 두 번째 칸 : ( preR, preC + 2^(N-1)) → cnt에 2^(N-1) x 2^(N-1) 을 더한다.
    • 세 번째 칸 : ( preR + 2^(N-1), preC ) → cnt에 2^(N-1) x 2^(N-1) x 2 를 더한다.
    • 네 번째 칸 : (preR + 2^(N-1), preC + 2^(N-1) ) → cnt에 2^(N-1) x 2^(N-1) x 3 를 더한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int n,r,c;
    public static void Setting() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
    }
    public static int solve(){
        int preR =0,preC =0;
        int nextR=0,nextC=0;
        int cnt=0;
        int len = (int)Math.pow(2,n);
        // len 은 2의 n승인 것들만 온다.
        while(len>2){
            len/=2;
            preR = nextR; preC = nextC;
            if( r< preR +len){
                // 첫 번째 칸
                if(c<preC +len){
                    nextR = preR;
                    nextC = preC;
                }
                // 두 번째 칸
                else{
                    nextR = preR;
                    nextC = preC + len;
                    cnt += (len*len);
                }
            }else{
                // 세 번째 칸
                if(c<preC +len){
                    nextR = preR +len;
                    nextC = preC;
                    cnt += (len*len)<<1;
                }
                // 네 번째 칸
                else{
                    nextR = preR +len;
                    nextC = preC + len;
                    cnt += (len*len)*3;
                }
            }
        }
        // nextR, nextC 에서 ,r,c의 위치를 찾아야함
        if(r<nextR+1){
            if(c<nextC+1)return cnt;
            else return cnt+1;
        }else{
            if(c<nextC+1)return cnt+2;
            else return cnt+3;
        }

    }
    public static void main(String[] args) throws IOException {
        Setting();
        int res = solve();
        System.out.println(res);
    }
}