Level 2. 멀리 뛰기

Level 2. 멀리 뛰기

 

 

피보나치 수열이다.

 

n번째 칸에 도달하는 방법은, 1칸 + (n - 1)번째에 도달하는 경우의 수와 2칸 + (n - 2)번째에 도달하는 경우의 수를 더한 것이다.

 

재귀를 활용하면 중복 계산이 여러 번 발생하므로 시간 초과가 발생한다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>

using namespace std;

long long rSolution(int n)
{
    if (n < 0)
        return 0;
    else if (n == 0)
        return 1;

    return rSolution(n - 1) + rSolution(n - 2);
}

long long solution(int n)
{
    return rSolution(n) % 1234567;
}

 

메모이제이션(혹은 DP)을 활용하면 하나의 경우에 대해 1번 만 계산할 수 있다.

 

#include <iostream>

using namespace std;

long long solution(int n)
{
    long long arr[2001] = {1, 1, };

    for (int i = 2; i <= n; ++i)
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;

    return arr[n];
}