[백준]1074 - Z 문제 풀이(Java,자바)

1074번: Z

들어가며

못푼 문제이다.

처음 접근은 배열을 다 만들고 위치를 찾는 건데

머리 터질 뻔했다.

 

코드

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


public class 백준1074_Z {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int r = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);

        int size = (int) Math.pow(2, n);  // 2^n 크기의 배열
        int count = find(size, r, c);
        System.out.println(count);
    }

    private static int find(int size, int r, int c) {
        // 기본 종료 조건
        if (size == 1) {
            return 0;  // 더 이상 나눌 수 없으면 해당 위치는 0번째
        }

        int half = size / 2;
        int area = size * size / 4;  // 한 영역의 크기

        // 사분면에 따라 호출하고, 해당 영역에 번호를 추가
        if (r < half && c < half) {
            return find(half, r, c);  // 1사분면
        } else if (r < half && c >= half) {
            return area + find(half, r, c - half);  // 2사분면
        } else if (r >= half && c < half) {
            return 2 * area + find(half, r - half, c);  // 3사분면
        } else {
            return 3 * area + find(half, r - half, c - half);  // 4사분면
        }
    }
}

풀이

문제를 아주 단순하게 볼 필요가 있다.

0	1
2	3

 

가장 기본인 2x2 행렬을 보자.

여기서 우리가 찾고 싶은 위치를 파악하는 방법은 뭘까??

 

바로 "사분면을 찾는 것"이다.

 

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

 

그렇다면 4x 4 행렬에선 3을 찾을려면 어떤 방식으로 진행을 해야 할까?

사분면을 찾으면 된다.

 

3은 1사분면이다.

1사분면을 찾고 나선 어떻게 해야할까??

그 1사분면을 다시 한번 보자

0	1
2	3

 

처음으로 돌아왔다. 

여기서도 사분면을 찾으면 된다.

3은 4사분면이 된다.

즉, 위와 같은 방법으로 찾고 싶은 r행 c열을 찾을 수 있다.

 

그렇다면 어떻게 숫자를 카운트할 수 있을까?

이것 또한 사분면을 잘 보면 할 수 있다.

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

 

0	1
2	3

3

계속 사분면을 분할하면서 결국 만들어지는 건 하나의 칸이다.

즉, 시작점을 파악을 한다면 값을 구할 수 있다.

 

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

또 문제가 생기는데 이 넓은 16칸의 네모에서 사분면이라는 정보만을 이용해서

2사분면의 시작점인 4를 어떻게 구할 수 있을까??..

 

구하는 방법은 바로 1사분면의 넓이가 곧 시작점인 4가 된다.

3사분면은? 한 사분면의 넓이의 2배를 더해주면 된다.

4사분면은? 한 사분면의 넓이의 3배를 더해주면 된다.

1사분면은? 아무 것도 할 필요가 없다.

 

즉, 사분면 하나의 넓이를 알게 된다면 값을 파악할 수 있다.

그렇다면 다음 사각형을 자르기 전에 한 사분면의 넓이를 계속 더해간다면

잘라짐으로써 초기화되는 위치들을 처리할 수 있게 된다.

 

private static int find(int size, int r, int c) {
    // 기본 종료 조건
    if (size == 1) {
        return 0;  // 더 이상 나눌 수 없으면 해당 위치는 0번째
    }

    int half = size / 2;
    int area = size * size / 4;  // 한 영역의 크기

    // 사분면에 따라 호출하고, 해당 영역에 번호를 추가
    if (r < half && c < half) {
        return find(half, r, c);  // 1사분면
    } else if (r < half && c >= half) {
        return area + find(half, r, c - half);  // 2사분면
    } else if (r >= half && c < half) {
        return 2 * area + find(half, r - half, c);  // 3사분면
    } else {
        return 3 * area + find(half, r - half, c - half);  // 4사분면
    }
}

 

그렇게 위와 같은 find 메서드가 만들어진다.