[BaekJoon/백준] 10830번 분할정복

1629번과 아주 똑같은 유형이다.

정수를 제곱하느냐 행렬을 제곱하느냐의 차이밖에 없다.

 

 

풀이 방향은 1629번과 동일하다.

#include <stdio.h>
#include <string.h>

int arr[5][5];
int original[5][5];

int N;
long long B;


// 재귀 속에서 정적 변수인 arr을 공용으로 사용하면서 업데이트해나감.
void pow_(long long k) {
    int i, j, m;

    int temp1[5][5];
    if(k == 1) {
        // 1일 경우, 2740번에서 a % c를 해줬던 것 처럼
        // 이 문제에서 주어진 조건은 각 원소값을 1000을 나눈값이어야 하므로, 이렇게 처리.
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++)
                arr[i][j] %= 1000;
        }
        return;
    }
    
    pow_(k / 2);
    
    // 재귀 결과 상태를 받아옴, int a = pow_(k / 2)라고 보면 됨.
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++)
            temp1[i][j] = arr[i][j];
    }
    
    // 비워주고
    memset(arr, 0, sizeof(arr));
    
    // 곱
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            for(m = 0; m < N; m++)
                arr[i][j] = (arr[i][j] + (temp1[i][m] * temp1[m][j])) % 1000;
        }
    }
    
    if(k % 2) {
        // temp1에 arr 결과값을 복사한 뒤
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++)
                temp1[i][j] = arr[i][j];
        }
        // arr을 다시 비워주고
        memset(arr, 0, sizeof(arr));
        
        // 곱
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++) {
                for(m = 0; m < N; m++)
                    arr[i][j] = (arr[i][j] + (temp1[i][m] * original[m][j])) % 1000;
            }
        }
        
    }
    
}

int main() {
    int i, j;
    
    scanf("%d %lld", &N, &B);
    
    
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            original[i][j] = arr[i][j];
        }
    }
    
    pow_(B);
    
    
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++)
            printf("%d ", arr[i][j]);
            
        putchar('\n');
    }
}

문제에서 주의할 점은

1. %1000

2. B는 int 보다 크다는 것.

 

 

 

 

문제의 방향성을 못잡겠다면 아래 글을 참고하면 좋을 것 같다.

yjyoon-dev.github.io/boj/2020/12/23/boj-10830/

gre-eny.tistory.com/46

claude-u.tistory.com/421