분할정복 알고리즘 예제

 

// 1. 라이브러리
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 2. 자료 구조


// 3. solve() --> 문제 풀이
// 분할 정복: N --> N-1
// T(N) = T(N-1) + O(1) ==> T(2^N) = T(2^(N-1)) + O(1)
int solve(int N, int x, int y) {
    // 0) 예외 처리: N == 1일 때
    if (N == 1) {
        if (x == 0 && y == 0)
            return 0;
        else if (x == 1 && y == 0)
            return 1;
        else if (x == 0 && y == 1)
            return 2;
        else if (x == 1 && y == 1)
            return 3;
        else
            return -1; // error!!
    }
    
    // 1) 분할: N --> N-1, (2^N x 2^N --> 2^(N-1)) 4분할
    int mid = N - 1;        // N = 8, mid = 7
    int half = pow(2, mid); // half: 2^(N-1), half = 2^7 = 128
    int half2 = half * half // 연산 횟수 줄여서 효율적 코드
    
    int new_x, new_y;       // 새로 4분할된 공간에서의 cell의 새로운 위치
    int offset;             // 건너뛰게되는 분할된 공간의 cell의 수
    
    if (x < half) { // x < 2^(N-1)
        if (y < half) { // y < 2^(N-1) --> x < half && y < half --> 0번째 구간
            new_x = x;
            new_y = y;
            offset = 0;
        }
        else {          // 2^(N-1) <= y --> x < half && y > half --> 2번째 구간
            new_x = x;
            new_y = y - half;
            offset = 2 * half2;     // 2 x 2^(N-1) x 2^(N-1)
        }
    }
    else {  // 2^(N-1) <= x
        if (y < half) { // y < 2^(N-1) --> half <= x && y < half --> 1번째 구간
            new_x = x - half;
            new_y = y;
            offset = half2;         // 2^(N-1) x 2^(N-1)
        }
        else {          // 4번째 구간
            new_x = x - half;
            new_y = y - half;
            offset = 3 * half2;
        }
    }
    
    // 2) 정복 & 3) 결합
    return solve(N - 1, new_x, new_y) + offset;
}

// 4. main() --> 입출력, solve () 호출, 결과 출력
int main() {
    // 1) 입출력
    FILE* fp;
    fopen_s(&fp, "input.txt", "r+t");
    int tc; // number of test case
    int a, b, c;
    int ans, sol;
    
    fscanf_s(fp, "%d", &tc);
    for (int i=0; i < tc; i++) {
        fscanf_s(fp, "%d %d %d", &a, &b, &c);
        fscanf_s(fp, "%d", &ans);
        
//      printf("%d %d %d\n", a, b, c);
//      printf("%d\n", ans);
        
        // 2) solve() 호출
        solve(a, b, c);
        
        // 3) 결과 출력
        if (ans == sol)
            printf("correct\n");
        else
            printf("wrong\n");
    }

    flose(fp);
    return 0;
}