[BOJ 16467 // C++] 병아리의 변신은 무죄

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16467번 문제인 병아리의 변신은 무죄이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16467

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

이 문제는 최대 100개의 테스트케이스에 대해서, 문제에서 주어진 점화관계를 이용해 최대 1억번째 항을 계산해내는 문제이다. 따라서 만약 점화관계를 그대로 반복계산해 나간다면, 시간초과가 날 수밖에 없다.

 

따라서 위와 같은 시간초과를 피하기 위해

1) 점화관계를 행렬의 곱으로 표현하고

2) 행렬의 거듭제곱을 binary exponentiation을 통해 빠르게 계산하는 방법을 이용해볼 수 있다.

 

이 문제에서 요구하는 점화식은 다음과 같은 단순한 형태이다.

(다음 날 병아리 수) = (오늘 병아리 수) + (K일 전날 병아리 수)

 

이 문제에서 modulo 연산을 요구하는 숫자가 1,000,000,007이 아닌 100,000,007임에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
typedef long long ll;

int main()
{
    int T; cin >> T;
    for (int t = 0;t < T;t++) {
        int K, N;
        cin >> K >> N;
        ll mat[12][12];
        ll ans[12];
        for (int i = 0;i <= K;i++) {
            ans[i] = 0;
            for (int j = 0;j <= K;j++) {
                mat[i][j] = 0;
            }
        }
        for (int i = 0;i < K;i++) {
            mat[i + 1][i] = 1;
        }
        mat[0][0] = 1;
        mat[0][K] += 1; // K=0인 경우 mat[0][0]에 1을 더하는게 맞다
        ans[0] = 1;
        while (N > 0) {
            if (N & 1) { // ans에 mat을 곱한다
                ll ans_t[11];
                for (int i = 0;i <= K;i++) {
                    ans_t[i] = 0;
                    for (int j = 0;j <= K;j++) {
                        ans_t[i] += mat[i][j] * ans[j];
                    }
                }
                for (int i = 0;i <= K;i++) {
                    ans[i] = ans_t[i]%100000007;
                }
            }
            // mat의 제곱을 구한다.
            ll mat_t[12][12];
            for (int i = 0;i <= K;i++) {
                for (int j = 0;j <= K;j++) {
                    mat_t[i][j] = 0;
                    for (int k = 0;k <= K;k++) {
                        mat_t[i][j] += mat[i][k] * mat[k][j];
                    }
                }
            }
            for (int i = 0;i <= K;i++) {
                for (int j = 0;j <= K;j++) {
                    mat[i][j] = mat_t[i][j]%100000007;
                }
            }
            N >>= 1;
        }
        cout << ans[0] << '\n';
    }

    return 0;
}