[백준/BOJ] 11401번 : 이항 계수 3, 10830번 : 행렬 제곱 (분할 정복, 빠른 거듭제곱)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11401번 : '이항 계수 3', 10830번 : '행렬 제곱' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 분할 정복(Divide and Conquer) 알고리즘에 대한 이해가 필요합니다.

 

 

11401번 : 이항 계수 3

 

N과 K가 400만 이하일 때 N C K를 구하는 문제입니다.

주어진 범위가 아주 크고 N!을 K!(N-K)!으로 나누어야하기 때문에 모듈로 연산을 해주기도 쉽지 않습니다.

따라서 여기서는 페르마의 소정리 및 빠른 거듭제곱 알고리즘을 사용하여 문제를 해결해주어야 합니다.

 

[백준/BOJ] 13977번 : 이항 계수와 쿼리 (페르마의 소정리)

↑ 페르마의 소정리에 대한 정리 포스트는 위의 링크를 참조해주시면 됩니다.

 

간단히 정리하면 N C K를 연산할 때 어차피 모듈로 연산을 해야하므로 페르마의 소정리를 활용하면 다음과 같이 된다는 것입니다.

 

N C K ≡ N! × ((N-K)!K!)^(m-2) (mod m)

 

따라서 위의 연산을 수행해주되 거듭제곱을 수행하는 과정에서 빠른 거듭제곱 알고리즘을 이용해 계산해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long fastPow(long long ret, int exp) {
    if(exp == 0) return 1;
    else if(exp == 1) return ret;

    if(exp % 2 == 0) {
        long long temp = fastPow(ret, exp/2);
        return (temp * temp) % MOD;
    }
    else {
        long long temp = fastPow(ret, exp - 1);
        return (temp * ret) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;
    vector<long long> factorial(N+1);
    factorial[0] = factorial[1] = 1;
    for(int i=2; i<=N; i++)
        factorial[i] = (factorial[i-1] * i) % MOD;

    cout << factorial[N] * fastPow((factorial[K] * factorial[N-K]) % MOD, MOD - 2) % MOD;
}

 

이를 풀이 코드로 작성하면 위와 같이 되며, 이 때 팩토리얼을 빠르게 연산해주기 위해 DP를 활용하여 팩토리얼 mod 값을 배열에 저장해주면서 계산해나가면 됩니다.

 

 

 

 

10830번 : 행렬 제곱

 

행렬을 거듭제곱하는 문제입니다.

요즘은 고등학교 교육 과정에서 행렬을 배우지 않는 것으로 아는데, 아무튼 행렬의 곱 연산에 대해 알고 있어야 문제 해결이 가능합니다.

 

거듭제곱의 경우 빠른 거듭제곱의 방식을 사용해주어야 시간 초과를 받지 않고 해결이 가능합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N;
long long arr[5][5], ans[5][5];

void multiply(long long a[5][5], long long b[5][5]) {
    long long temp[5][5] = {};

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
                temp[i][j] = (temp[i][j] + a[i][k]*b[k][j]) % 1000;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) a[i][j] = temp[i][j];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    long long Exp; cin >> N >> Exp;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            cin >> arr[i][j];
            if(i == j) ans[i][j] = 1;
        }

    while(Exp > 0) {
        if(Exp%2 == 1) multiply(ans, arr);
        multiply(arr, arr);
        Exp /= 2;
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++)
            cout << ans[i][j] << " ";
        cout << "\n";
    }
}

 

matrix나 operate 연산자 오버라이딩을 사용하여 문제를 푸는 사람들이 많은 것으로 아는데, 굳이 그렇게 구현하지 않아도 위처럼 단순하게 풀이가 가능합니다.

ans에 답을 구한다고 할 때, arr을 위의 while문과 같이 곱하여 빠른 거듭제곱을 구현할 수 있습니다.

 

예를 들어 ans = arr^5로 만들어야 한다고 할 때, 5는 이진수로 101이므로 arr^4에 arr을 곱해주면 됩니다.

따라서 ans에 arr^1을 곱해주고, 한편으로는 arr을 계속 거듭제곱 해주어 (arr^2)^2을 만들어줍니다.

그리고 마지막에 ans = arr에 arr^4를 곱해서 arr^5를 만들어주는 것입니다.

이러한 방식으로 log N 시간에 arr^N을 연산해줄 수 있습니다.