[프로그래머스] 2 x n 타일링 - 피보나치수열

문제

 

풀이

#include <string>
#include <vector>

using namespace std;

// 피보나치수열
// 1 > 2 > 3 > 5 > 8 > ...
int num = 1000000007;

int solution(int n) {
    int bf = 1;
    int af = 1;
    int temp;
    for(int i=1; i<n; i++){
        temp = af;
        af = (bf + af)%num;
        bf = temp%num;
    }
    
    return af%num;
}

f(1) : 1

f(2) : 2

f(3) : 3

f(4) : 5

f(5) : 8  ...

문제의 결괏값이 피보나치수열을 이루는 것을 확인할 수 있다.

 

피보나치 수열을 구하는 알고리즘을 활용하여 풀어주었다.

---

다른 사람 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) 
{
    int answer = 0;

    std::vector<int> vVal;
    vVal.clear();
    vVal.resize(n + 1);

    vVal[0] = 0;
    vVal[1] = 1;
    vVal[2] = 2;

    int Idx = 3;
    while ( Idx < n + 1 )
    {
        vVal[Idx] = ( vVal[Idx - 1] + vVal[Idx - 2] ) % 1000000007;
        ++Idx;
    }

    answer = vVal[Idx - 1] ;

    return answer;
}