문제 링크입니다: http://poj.org/problem?id=3070
TILING2(http://jaimemin.tistory.com/323?category=985009)를 풀고 비슷한 문제인 TILING 문제를 풀려다가 보기 좋게 실패했습니다.
점화식을 유도해서 행렬을 이용하여 풀면 된다고 하지만 아직 공부가 부족해서인지 풀이를 보고도 이해가 가지 않았습니다.
https://algospot.com/forum/read/903/가 풀이인데 행렬을 이용하는 것이 이해가 가지 않는다면 PKU 3070을 풀어보면 이해가 된다고 해서 한번 풀어봤습니다.
(희망사항: 1권을 끝내고 나면 TILING을 풀 수 있는 실력이 되기를...)
/*
F(0)=0, F(1)=1일 때 피보나치 수열은 F(n)=F(n-1)+F(n-2)이다 (n>=2)
이 때 행렬을 사용하면
┌F(n+1) F(n)┐= ┌1 1┐
└F(n) F(n-1)┘ └1 0┘의 n 승
n이 주어졌을 때 F(n)의 마지막 4자리 수를 구하시오
*/
#include <iostream>
#include <cstring> //memset
using namespace std;
const int MAX = 2;
const int MOD = 10000;
class Fibonacci
{
private:
int F[MAX][MAX];
public:
Fibonacci()
{
memset(F, 0, sizeof(F));
}
Fibonacci &operator*(Fibonacci &temp) //곱하기 연산자 정의
{
Fibonacci result;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
result.F[i][j] = 0;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int k = 0; k < MAX; k++)
result.F[i][j] += (F[i][k] * temp.F[k][j]) % MOD; //중요
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
F[i][j] = result.F[i][j];
return *this;
}
int *operator[](int i)
{
return F[i];
}
int answer(void) //F[0][1]에 있는 숫자가 답
{
return F[0][1];
}
};
Fibonacci formula, base;
void initialize(void) //초기화
{
formula[0][0] = formula[0][1] = formula[1][0] = 1;
formula[1][1] = 0;
base[0][0] = base[1][1] = 1;
base[0][1] = base[1][0] = 0;
}
Fibonacci pow(Fibonacci &f, int n)
{
if (n == 0)
return base;
else if (n == 1)
return formula;
if (n % 2 > 0)
return pow(f, n - 1)*f;
Fibonacci half = pow(f, n / 2);
return half*half;
}
int main(void)
{
int n;
Fibonacci result;
do
{
cin >> n;
if (n < 0 || n>1000000000)
exit(-1);
initialize();
result = pow(formula, n);
cout << result.answer()%MOD << endl << endl;
} while (n != -1);
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
*여기는 algospot보다 제약이 심하네요. 답을 출력할 때 개행을 한번만 하지 않으면 'presentation error'라고 뜹니다. 따라서 endl은 한번만 작성하시면 될 것 같습니다.