[BaekJoon/백준] 1074번 C++ 분할정복

분할정복 관련 문제다.

 

하지만 주의사항이 있다.

 

분할정복은 맞는데,
분할정복으로 모든 곳을 돌아서 값을 채우고, 그 배열을 이용하려 하면 시간초과가 날 것이다.
최대크기 32568 x 32578은 10억이 넘는다. 시간복잡도 O(n)에서 10억이면 10초정도 예상된다.

 

따라서 분할했을 때, 해당 섹션을 방문하지 않고도, 계산에 문제가 없도록
섹션의 크기를 계산해내는것이 중요하다.

문제에서 n을 입력 받을 때 변의 길이 = 2^n 역할의 n을 입력받으므로

1. 4^(n - 1)을 구역(섹션) 당 크기로 계산해도 되겠고

2. (현재 변의 길이 / 2)^2 을 구역 당 크기로 계산해도 되겠다.

#include <cstdio>
#include <iostream>
#include <math.h>

using namespace std;

int N, C, i, j;
int position;


// x : 전체를 4 구역으로 나눴을 때, 섹션 크기를 구하기 위해 사용되는 변수
// 즉 4구역을 나눴을 때, 문제에서 각 구역의 시작 수를 말함.
// n : 한 변의 길이
void real(int x, int n) {
    
    if(n == 1)
        return;
    
    int en = pow(4, x - 1);
    
    int A_START = 0;
    int B_START = en;
    int C_START = en * 2;
    int D_START = en * 3;
    
    if(i <= n / 2 - 1 && j <= n / 2 - 1) {
        // SECTION A
        position += A_START;
    } else if(i <= n / 2 - 1 && j <= n - 1) {
        // SECTION B
        position += B_START;
        j -= n / 2;
    } else if(i <= n - 1 && j <= n / 2 - 1) {
        // SECTION C
        position += C_START;
        i -= n / 2;
    } else if(i <= n - 1 && j <= n - 1) {
        // SECTION D
        position += D_START;
        i -= n / 2; j -= n / 2;
    }
    real(x - 1, n / 2);
}

int main() {
    
    scanf("%d", &N);
    scanf("%d %d", &i, &j);
    
    C = N;
    N = pow(2, N); // 한 변의 크기
    
    real(C, N);
    
    
    printf("%d", position);
}

 

 

그리고 코드 흐름이 다소 간결하지 못한 것 같아서, 다른 사람들의 풀이도 참고해보고 조금 더 간결하게 구현해보았다.

 

우선 좀 더 간단하게 생각해보면, 2차원배열의 각 값을 '건너뛴 횟수' 라고 볼 수 있다.

그리고 이를 토대로

(3, 1) 위치의 값은 11이고, 이는 건너뛴 횟수가 11이라는 것이다.

 

저번에도 노력했지만 분할정복 코드를 짤 때

함수(시작x, 시작y, 변의길이) 이런식으로 짜려고 노력하기로 마음먹은 적이 있었다.

이렇게 하면 분할이 되게 간결하게 이루어지기도 한다.

 

이런식으로 함수 틀을 지정하고,

각 분할로 재귀를 돌 때 마다, 지정된 영역 안에 우리가 원하는 좌표가 존재하는지를 판별하고

없다면 해당 영역의 크기(즉, 이는 건너뛸 크기이다)를 전체 계산값에 더해주면서 '얼마나 건너뛰어야 할지'를 값으로 얻을 수 있고

그렇게 분할을 하다가 시작 좌표가 우리가 찾는 좌표와 같다면(이 때 변의길이 n도 1이겠죠?) 쌓아온 값을 출력해준 뒤 종료하면 된다.

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;


int N;
int i, j;

int result;


// x, y는 섹션 시작 좌표, n은 한 변의 길이
void divide(int x, int y, int n) {
    
    if(x == i && y == j) {
        printf("%d", result);
        exit(0); // 찾았으므로 끝
    }
    
    // 현재 영역에서 해당 좌표를 포함하고 있다면
    if(i <= x + n - 1 && j <= y + n - 1)
        ;// 아무작업도 안함.
    else {
        //현재 들어온 영역은 해당되지 않는다는 것이므로, 해당 영역의 자리크기만큼 스킵하기 위해 연산.
        result += n * n;
        return;
    }
    
    divide(x, y, n / 2); // SECTION A
    divide(x, y + n / 2, n / 2); // SECTION B
    divide(x + n / 2, y, n / 2); // SECTION C
    divide(x + n / 2, y + n / 2, n / 2); // SECTION D
    
}

int main() {
    
    scanf("%d", &N);
    scanf("%d %d", &i, &j);
    
    divide(0, 0, pow(2, N));
}

 

문제의 흐름이 이해가 가지 않는다면 아래 블로그들을 읽어볼 것을 추천드립니다!

개념 설명 : mygumi.tistory.com/284  simsimjae.tistory.com/191

코드 풀이 설명 : donggoolosori.github.io/2020/09/22/boj-1074-Z/