[백준 1074] Z (JAVA)

백준 1074번 문제 - Z

1074번: Z

---

문제 분석

 

 

• 2^(n-1) 크기에 배열에 위에 그림처럼 Z모양 순(왼 위, 왼 아래, 오 위, 오 아래) 으로 방문한다.
• 이 때 r행 c열은 몇 번째로 방문했는지 출력해라.

---

해결 포인트

 

•  합병 정렬 사용
  • 몇번째 사분면에 존재하는지 판단
  • 해당 사분면 가기 전에 이전 앞서 방문해야 하는 개수
    ( size 는 한 변의 길이 → size * size 는 전체 배열 개수 )
    - 1사분면 : 0
    - 2사분면 : size *size / 4 * 1
    - 3사분면 : size *size / 4 * 2
    - 4사분면 : size *size / 4 * 3
  •  size 가 1일때까지 반복
    : size를 절반으로 줄이고 위치로 해당 사분면만 따지도록 변경

 

---

코드

 

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

public class Main {
    public static int N,r,c;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int size = (int) Math.pow(2, N);

        bw.write(find(size, r, c) + "\n");

        bw.flush();
        bw.close();
    }

    public static int find(int size, int r, int c) {
        if(size == 1) return 0;

        // 1사분면
        if(r < size/2 && c < size/2) {
            return find(size/2, r, c);
        }
        // 2사분면
        if(r < size/2 && c >= size/2) {
            return find(size/2, r, c-size/2) + (size * size / 4);
        }
        // 3사분면
        if(r >= size/2 && c < size/2) {
            return find(size/2, r-size/2, c) + (size * size / 4 * 2);
        }
        // 4사분면
        return find(size/2, r-size/2, c-size/2) + (size * size / 4 * 3);
    }
}