[백준] 1074 Z

https://www.acmicpc.net/problem/1074

1074번: Z

2021-07-13

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1074 {
    public static int N, r, c;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int answer = 0;
 
        int x = (1 << N) >> 1; // init
        int y = x;
 
        while(N-- > 0) {
            int quarter =  (1 << N) * (1 << N);
            int move = (1 << N) >> 1;
            if (r < x && c < y) { // 1
                x -= move;
                y -= move;
            } else if (r < x && c >= y) { // 2
                x -= move;
                y += move;
                answer += quarter;
            } else if (r >= x && c < y) { // 3
                x += move;
                y -= move;
                answer += quarter*2;
            } else {
                x += move;
                y += move;
                answer += quarter*3;
            }
        }
 
        System.out.println(answer);
    }
}

 

#문제풀이

분할정복 문제이다,,  개인적으로 이게 실버1? 인지 잘 모르겠는 문제이다..

1,2,3,4 분면을 나눠서 범위를 좁혀 나가는게 포인트인 문제이다. 

 

두 번째 예제 N == 3, r == 7, c == 7 을 기준으로 본다.

처음 초기값(x, y)은 정중앙인 2^N / 2 ((1<< N) >> 1) 으로 잡았다. 

그리고 4개의 사분면은 아래와 같은 방법으로 나눌 수 있다.

그리고 원하는 지점(7, 7)을 찾을 때까지, 해당 사분면에서 또 다시 4등분으로 나누면 된다.

또한, 여기서 각 사분면의 중심점이 새로 바뀐 것을 아래와 같이 확인할 수 있다.

이 때, 기준은 초기값과 같이  2^N / 2 ((1<< N) >> 1) (->move)이다.

 

1사분면  : (x -= 2, y-=2)

2사분면 : (x-=2, y+=2)

3사분면 : (x+=2, y-=2)

4사분면 : (x+=2, y+=2)

또한, 각 사분면이 움직일 때마다 더해야하는 수가 있다.

예를 들어, 내가 찾아야하는 (r, c)가 3사분면 쪽에 있다면, 1+2 사분면에서 계산해야하는 값들을 더한 후 이동해야 된다. 왜냐하면 우리가 어차피 3사분면에 이동하기 전까지 1+2사분면에서 카운팅 되는 숫자는 정해져있기 때문이다. 그래서 1사분면은 이동해야할 숫자를 더할 필요가 없다.

그리고 이것이 2^N (1<< N)*(1 << N)  (->quarter)인 것을 알 수 있다.

 

1사분면 : x

2사분면 : (1<<N)*(1<<N)

3사분면 : (1<<N)*(1<<N) * 2

4사분면 : (1<<N)*(1<<N) * 3

 

이것들을 N이 0이 될 때까지 반복하면 된다.