[C++]백준 - 11444번 문제

11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

 

11444번 : 피보나치 수 6

---

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

 

 

출력

---

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

 

 

---

 

생각해 볼 점

---

피보나치 수를 구하는 방법은 기존에 재귀 함수, 동적 계획법을 이용해서 구해보았습니다.

 

하지만, 재귀 함수를 이용하면 수행 시간이 너무 오래 걸리고

동적 계획법을 이용하려면 n의 값에 해당하는 배열 공간이 필요합니다.

 

그리고 이 문제는 n의 최댓값이 1,000,000,000,000,000,000이나 되는 입력을 받습니다.

 

따라서, 우리는 행렬의 멱법을 통해 이 문제를 해결할 수 있습니다.

 

행렬의 멱법을 통해 피보나치 F(n)을 구하는 방법은 아래와 같습니다.

이 공식을 이용, 분할정복을 통해 F(n)의 값을 구할 수 있습니다. 그 과정에서 1,000,000,007의 나머지의 형태를 유지해 주는 것은 잊지 않도록 합시다.

 

전체적으로 풀이는 10830번 문제와 유사합니다.

 

 

코드

---

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;

ll N;

//곱셈 연산자 오버로딩
matrix operator *(const matrix &A, const matrix &B)
{
    matrix ret;
    ret.assign(2, vector<ll>(2));
    for(ll i = 0; i < 2; i ++)
    {
        for(ll j = 0; j < 2; j++)
        {
            for(ll k = 0; k < 2; k++)
            {
                ret[i][j] += A[i][k] * B[k][j];
                ret[i][j] %= 1000000007;
            }
        }
    }
    return ret;
}

//재귀 함수
matrix solution(ll N)
{
    if(N == 1)
    {
        matrix ret = {{1,1}, {1,0}};	//행렬의 멱법을 이용한 풀이
        return ret;
    }
    if(N % 2 == 0)
    {
        matrix temp = solution(N / 2);
        return temp * temp;
    }
    matrix temp = {{1,1},{1,0}};
    return solution(N-1) * temp;
}


int main()
{
    cin >> N;
    cout << solution(N)[0][1];	//F(n)은 [0][1] 혹은 [1][0] 두 개가 동일한 값임.
    return 0;
}

 

그 외

---

행렬의 멱법은 이전에 배운 적이 있었지만, 바로 생각나지 않아 인터넷을 뒤져서 풀었습니다.

실무에서 쓸모있을 지는 모르겠지만, 외워두도록 해야겠습니다.