이 문제에서는 정수 N과, N번째 항을 이전 항들의 함수로 정의하는 재귀 관계식(점화식)이 주어집니다. 우리의 목표는 행렬 거듭제곱(Matrix Exponentiation) 기법을 활용해 N번째 항을 구하는 프로그램을 작성하는 것입니다.
주어진 점화식은 다음과 같습니다.
T(n) = 2 * T(n-1) + 3 * T(n-2)
초기값: T(0) = 1, T(1) = 1
문제 예시
입력
N = 4
출력
41
풀이 과정
T(4) = 2 * T(3) + 3 * T(2)
T(4) = 2 * (2 * T(2) + 3 * T(1)) + 3 * (2 * T(1) + 3 * T(0))
T(4) = 2 * (2 * (2 * T(1) + 3 * T(0)) + 3 * 1) + 3 * (2 * 1 + 3 * 1)
T(4) = 2 * (2 * (2 + 3) + 3) + 3 * 5
T(4) = 2 * (10 + 3) + 15
T(4) = 26 + 15 = 41
방법 1: 단순 재귀
가장 직관적인 방법은 재귀 호출입니다. 초기값 T(0)과 T(1)을 기저 조건(base case)으로 설정하고, N번째 항을 이전 두 항의 재귀 호출로 계산합니다.
다만 이 방법은 같은 항을 중복 계산하기 때문에 시간 복잡도가 지수적으로 증가한다는 단점이 있습니다.
구현 코드
#include <iostream>
using namespace std;
long calcNthTerm(long n) {
if(n == 0 || n == 1)
return 1;
return ( ( 2*(calcNthTerm(n-1)) ) + ( 3*(calcNthTerm(n-2)) ) );
}
int main() {
long n = 5;
cout<<n<<"th term of found using matrix exponentiation is "<<calcNthTerm(n);
return 0;
}
실행 결과
5th term of found using matrix exponentiation is 121
방법 2: 행렬 거듭제곱 (효율적 접근)
더 효율적인 방법은 행렬 거듭제곱 개념을 활용하는 것입니다. 이 방법에서는 점화식을 변환 행렬(Transform Matrix) 형태로 변환한 뒤, 행렬의 거듭제곱을 통해 N번째 항을 빠르게 구합니다.
변환 행렬 구성하기
변환 행렬의 크기는 의존하는 이전 항의 개수에 따라 결정됩니다. 이 문제에서는 이전 항이 2개이므로 2×2 크기의 변환 행렬을 사용하며, 초기값은 T(0) = 1, T(1) = 1입니다.
크기가 k×k인 변환 행렬(TM)을 크기가 k×1인 초기 행렬(IM)과 곱하면 다음 항들을 얻을 수 있습니다.
초기 행렬(IM):
| 1 | ← T(1)
| 1 | ← T(0)
변환 행렬(TM):
| 2 3 |
| 1 0 |
이때 N번째 항은 다음과 같이 계산됩니다.
[ T(n) ] = TM^(n-1) × IM
[ T(n-1) ]
즉, 변환 행렬을 (n-1)제곱한 뒤 초기 행렬과 곱하면 결과 벡터의 첫 번째 성분이 T(n)이 됩니다. 행렬 거듭제곱은 분할 정복(반복 제곱법)을 사용해 O(log N) 시간에 계산할 수 있으며, 값이 너무 커지는 것을 막기 위해 모듈러 연산(MOD = 1000000009)을 적용합니다.
구현 코드
#include <iostream>
using namespace std;
#define MOD 1000000009
long calcNthTerm(long n) {
if (n <= 1)
return 1;
n--;
long resultantMat[2][2] = { 1, 0, 0, 1 };
long transMat[2][2] = { 2, 3, 1, 0 };
while (n) {
long tempMat[2][2];
if (n & 1) {
tempMat[0][0] = (resultantMat[0][0] * transMat[0][0] +
resultantMat[0][1] * transMat[1][0]) % MOD;
tempMat[0][1] = (resultantMat[0][0] * transMat[0][1] +
resultantMat[0][1] * transMat[1][1]) % MOD;
tempMat[1][0] = (resultantMat[1][0] * transMat[0][0] +
resultantMat[1][1] * transMat[1][0]) % MOD;
tempMat[1][1] = (resultantMat[1][0] * transMat[0][1] +
resultantMat[1][1] * transMat[1][1]) % MOD;
resultantMat[0][0] = tempMat[0][0];
resultantMat[0][1] = tempMat[0][1];
resultantMat[1][0] = tempMat[1][0];
resultantMat[1][1] = tempMat[1][1];
}
n = n / 2;
tempMat[0][0] = (transMat[0][0] * transMat[0][0] +
transMat[0][1] * transMat[1][0]) % MOD;
tempMat[0][1] = (transMat[0][0] * transMat[0][1] +
transMat[0][1] * transMat[1][1]) % MOD;
tempMat[1][0] = (transMat[1][0] * transMat[0][0] +
transMat[1][1] * transMat[1][0]) % MOD;
tempMat[1][1] = (transMat[1][0] * transMat[0][1] +
transMat[1][1] * transMat[1][1]) % MOD;
transMat[0][0] = tempMat[0][0];
transMat[0][1] = tempMat[0][1];
transMat[1][0] = tempMat[1][0];
transMat[1][1] = tempMat[1][1];
}
return (resultantMat[0][0] * 1 + resultantMat[0][1] * 1) % MOD;
}
int main() {
long n = 5;
cout<<n<<"th term of found using matrix exponentiation is "<<calcNthTerm(n);
return 0;
}
실행 결과
5th term of found using matrix exponentiation is 121
두 방법의 비교
단순 재귀 방식은 구현이 간단하지만 중복 계산으로 인해 시간 복잡도가 O(2ⁿ)까지 증가할 수 있습니다. 반면 행렬 거듭제곱 방식은 분할 정복을 통해 행렬을 제곱하므로 시간 복잡도가 O(log N)으로, N이 매우 큰 경우에도 효율적으로 동작합니다. 따라서 큰 N에 대해 선형 점화식의 항을 구해야 한다면 행렬 거듭제곱이 가장 적합한 선택입니다.