1074 - Z

1. 서론

분할정복 문제이다. 완전탐색 할 경우 연산 횟수는 2^15 * 2^15인데 약 10억이므로 완전탐색으로 푼다면 시간초과가 나는 문제이다.

처음에 문제 이해를 잘못해서, 푸는데 애를 먹었다.

예시만 보고나서는, 2^N-1 * 2^N-1 크기의 박스 4개로 나눈 후, 각 박스별로 z형태로 2*2크기씩 진행하는것으로 이해했다.

좌측이 문제에서 요구하는 답안이고, 오른쪽이 처음에 잘못 이해했던 진행 방식이다. 복사 붙여넣기로 만든 이미지이므로 숫자는 빼고 어떤 방식으로 진행되는지만 보면 된다. 잘못된 예시를 다 그리지는 않았다.

그래서 4번이나 틀린 후에야.. 애초에 문제에서 요구하는 방식의 풀이가 아니란것을 깨달았다.

이해하고나서는, 알고리즘이 어렵지는 않았다. Top-down 방식으로 반복문을 이용해 풀이했다.

2. 풀이

이 문제의 포인트는 결국 계속해서 탐색을 할 때 마다 해당 수가 어떤 사분면에 있는지 찾아나가면 된다.

1. 먼저 각 사분면의 좌상단에 위치한 최소수를 찾는다.

문제에서 주어진 예시에서 살펴보면 각각 0, 16, 32, 48이다. 해당 수도 쉽게 찾을 수 있다.

사분면 번호 * 각 사분면의 크기이다.

위의 예시로 보면, 좌측 위 부터 0 1 2 3 사분면이라고 생각했을 때

0 사분면 -> 0 * 2^2 * 2^2 = 0

1 사분면 -> 1 * 2^2 * 2^2 = 16

.

.

와 같은 형태로 구할 수 있다.

2. 이제 주어진 좌표가 어떤 사분면에 속하는지 알아낸 후, 해당 사분면의 최소수로 답을 업데이트 해준다.

0 1 2 3 사분면으로 치환하면, r c를 이용해 쉽게 구할 수 있다.

int target = 0;
for (int j = N - 1; j >= 0; j--)
{
    int[] piece = new int[4];
    for (int i = 0; i < 4; i++) piece[i] = i * (1 << (2 * j));
    int row = r / (1 << j);
    int col = c / (1 << j);
    int idx = row * 2 + col;
    target += piece[idx];
    r -= row * (1 << j);
    c -= col * (1 << j);
    if (r <= 1 && c <= 1) {
          target += r * 2 + c;
        break;
    }
}

idx가 사분면이된다. 제곱 연산을 할 때 Math.pow 대신 비트 시프트 연산을 사용한 이유는, pow는 리턴 형태가 double 이므로 int형으로 사용하기위해 시프트 연산을 이용했다.

이후, 해당 사분면의 좌표로 치환해주어야 한다.
박스의 가로, 세로 길이가 j만큼 줄어들었으므로, r과 c에서 그만큼 빼주면 된다.
r -= row * (1 << j)
c -= col * (1 << j)

3. 종료조건

종료조건은, 사분면의 크기가 최소 크기인 1*1에 도달했을 때다. 그 때는 r과 c가 모두 1보다 작거나 같을 때 이므로, 종료조건을 추가해준다.

int target = 0;
for (int j = N - 1; j >= 0; j--)
{
    int[] piece = new int[4];
    for (int i = 0; i < 4; i++) piece[i] = i * (1 << (2 * j));
    int row = r / (1 << j);
    int col = c / (1 << j);
    int idx = row * 2 + col;
    target += piece[idx];
    r -= row * (1 << j);
    c -= col * (1 << j);
    if (r <= 1 && c <= 1) {
          target += r * 2 + c;
        break;
    }
}

종료조건에 도달한 이후, 최소 사분면에서 마지막 사분면 연산을 해주면 답이 나오게 된다.
다만, N == 1일 경우 애초에 반복문을 실행하지 않기 때문에, 따로 N이 1일 때 예외처리를 해주었다.

package backjoon;

import java.util.Arrays;
import java.util.Scanner;

public class P_1074_ver2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] inputs = Arrays.stream(scan.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = inputs[0];
        int r = inputs[1];
        int c = inputs[2];
        if (N == 1)
            System.out.println(r * 2 + c);
        else {
            int target = 0;
            int[] piece;
            for (int j = N - 1; j >= 0; j--)
            {
                piece = new int[4];
                for (int i = 0;i < 4; i++) piece[i] = i * (1 << (2 * j));
                int row = r / (1 << j);
                int col = c / (1 << j);
                target += piece[row * 2 + col];
                r -= row * (1 << j);
                c -= col * (1 << j);
                if (r <= 1 && c <= 1) {
                    target += r * 2 + c;
                    break;
                }
            }
            System.out.println(target);
        }
    }
}

끝