BOJ 백준 16467번 병아리의 변신은 무죄

 

BOJ 백준 16467 병아리의 변신은 무죄

 

문제: https://www.acmicpc.net/problem/16467

16467번: 병아리의 변신은 무죄

 

 

병아리가 매일마다 혼자서 알을 한 개씩 낳고 이 알은 K일 후에 부화할 때, N일이 지난 후의 병아리 수를 구하는 것이 문제이다.

 

 

 

개인적으로 이런 유형의 문제는 우선 관찰을 자세히 하는 것이 중요하다고 생각한다. K = 0일 때와 K = 1일 때를 한 번 살펴봤다. K = 0일 때는 i일 후의 병아리의 수를 2의 거듭제곱 꼴로 나타낼 수 있고, 이는 전날의 병아리 수를 두 번 더한 것이 기준일의 병아리 수와 같다는 것이다. K = 1일 때는 병아리 수를 구하는 식이 피보나치 수열을 구하는 점화식과 동일하다.

 

 

 

K가 임의의 값일 때 병아리 수를 구하는 식을 일반화 해보면 다음과 같다.

 

 

 

(i일 때의 병아리 수) = (i - K - 1일 때의 병아리 수) + (i-1일 때의 병아리 수)

 

 

dp[i]: i일이 지났을 때의 병아리 수

dp[i] = dp[i - K - 1] + dp[i - 1]

 

 

 

i - K - 1일에 있던 병아리가 그 다음 날에 알을 낳고 그 알이 K일 후에 병아리로 태어난다는 점을 고려하면 위의 점화식이 나온다는 걸 알 수 있다.

 

 

 

일반적으로 이런 비슷한 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 풀 수 있지만, 이 문제는 N의 최댓값이 1억인 데다가 테스트 케이스 수의 최댓값도 100이어서 주어진 시간 1초 안에 linear 하게 탐색하여 구할 수 없다. 그래서 분할 정복을 이용한 행렬의 거듭제곱을 이용하여 피보나치 수열의 값을 구한 것과 유사한 방식으로 해결해야 한다.

 

 

 

행렬의 거듭제곱을 이용한 선형 점화식의 다이나믹 프로그래밍(Dynamic Programming) 해결 방법에 관한 자세한 내용은 아래 링크의 블로그를 참조하면 유용하다.

 

 

 

링크: https://driip.me/00556a4c-0782-4c5b-a86a-8e27e5f4ac1b

행렬 거듭제곱을 이용한 선형 점화식의 DP 풀기

 

 

 

서술의 편의상 dp[i]를 F[i]로 치환하면, F[i] = F[i - 1] + F[i - K - 1]의 식이 나온다. 그리고 F[i - 1] = F[i - 1], F[i - 2]= F[i - 2], ...임을 이용하여 행과 열의 수가 K + 1인 정방행렬 A를 지닌 행렬의 곱셈 식으로 표현하면 다음과 같다.

 

 

K의 제한은 10으로 크지 않으므로 F[0]부터 F[K]까지는 직접 구하고, 위에서 설명한 분할 정복을 이용한 행렬의 거듭제곱을 이용하여 정방행렬 A의 N - K 제곱을 시간 복잡도 O(logN) 안에 계산한다.

 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using matrix = vector<vector<ll>>;

const ll MOD = (ll)1e8 + 7;
const int K_MAX = 10;

int t, k, n;
ll f[K_MAX + 1];

matrix operator *(const matrix& a, const matrix& b){
    int size1 = (int)a.size();
    int size2 = (int)b.size();
    int size3 = (int)b[0].size();
    
    matrix c(size1, vector<ll>(size3, 0));
    
    for (int i = 0; i < size1; i++){
        for (int j = 0; j < size3; j++){
            for (int k = 0; k < size2; k++){
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= MOD;
            }
        }
    }
    
    return c;
}

matrix exp_matrix(int x){
    matrix a(k + 1, vector<ll>(k + 1, 0));
    matrix ret(k + 1, vector<ll>(k + 1, 0));
    
    for (int i = 0; i <= k; i++){
        ret[i][i] = 1;
    }
    a[0][0] = a[0][k] = 1;
    
    for (int i = 1; i <= k; i++){
        a[i][i - 1] = 1;
    }
    
    while(x){
        if (x % 2){
            ret = ret * a;
        }
        a = a * a; x /= 2;
    }
    return ret;
}

ll exp_two(int x){
    ll ret = 1, a = 2;
    while(x){
        if (x % 2){
            ret *= a;
            ret %= MOD;
        }
        a *= a; a %= MOD; x /= 2;
    }
    return ret;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &k, &n);
        
        if (k == 0){
            printf("%lld\n", exp_two(n) % MOD);
            continue;
        }
        
        f[0] = 1;
        for (int i = 1; i <= k; i++){
            f[i] = f[i - 1];
            if (i - k - 1 >= 0){
                f[i] += f[i - k - 1];
            }
        }
        
        if (n <= k){
            printf("%lld\n", f[n] % MOD);
            continue;
        }
        
        matrix res(k + 1, vector<ll>(k + 1, 0));
        res = exp_matrix(n - k);
        
        matrix x(k + 1, vector<ll>(1, 0));
        matrix ans(k + 1, vector<ll>(1, 0));
        
        for (int i = 0; i <= k; i++){
            x[i][0] = f[k - i];
        }
        
        ans = res * x;
        printf("%lld\n", ans[0][0]);
    }
    
    return 0;
}