[백준 1074번] [분할정복] Z

 

이 문제를 보고 분할정복으로 느껴야하는 이유는 다음과 같다.

전체 횟수는 각 배열을 4등분 한 것의 합으로써 구성이 되기에 결과적으로는 각 분할된 것들을 처리해주고 한번에 더해주는 방식으로 몇번째로 방문하는지를 체크해주면 된다.

 

단, 이 상황에서 시작점의 x좌표와 y좌표를 기록을 하면서 길이를 게속해서 고려해야하므로 재귀함수의 인자에 x좌표, y좌표, 길이가 들어가 있어야 한다.

추가적으로 4개의 조각 중에 어느 곳에 해당하는지를 찾기 위해서 문제에서 주어진 r와 c 값을 parameter로 가지면 된다.

 

Recursion function에서 base case는 length가 2인 케이스를 기준으로 구분해 주면 된다.

 

해당하는 방법으로 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int checker(int r, int c, int start_y, int start_x, long long length){
    int count = 0;

    // Base case

    if (length == 2){
        if(r == start_y){
            if(c != start_x) count += 1;
        }
        else{
            if(c != start_x) count += 3;
            else count += 2;
        }
        return count;
    }
    
    // 1사분면 or 2사분면
    if (start_y + length / 2 > r){
        // 2사분면
        if(start_x + length / 2 > c){
            count += checker(r, c, start_y, start_x, length / 2);
        }
        // 1사분면
        else{
            count += length * length / 4;
            count += checker(r, c, start_y, start_x + length / 2, length / 2);

        }

    }
    // 3사분면 or 4사분면
    else{
        // 3사분면
        if(start_x + length / 2 > c){
            count += length * length / 4 * 2;
            count += checker(r, c, start_y + length / 2, start_x, length / 2);

        }
        // 4사분면
        else{
            count += length * length / 4 * 3;
            count += checker(r, c, start_y + length / 2, start_x + length / 2, length / 2);
     
        }

    }

    return count;

}
int main(void){
    int n, r, c;
    cin >> n >> r >> c; // input data
    long long length = pow(2, n);
    cout << checker(r, c, 0, 0 , length) << "\n";

    return 0;
}

단, length는 2^15까지 가능하므로 long long 자료형으로 처리해주어야 한다는 점을 유의해야 한다.

(항상, 맨 마지막에 자료형이 커버할 수 있는 정도를 체크하고 계산할 것!!)