멀리 뛰기

문제

문제 풀이

1. 처음에는 DFS로 풀 생각을 했다.

예제와 동일하게 칸 수가 4인 경우에 대한 경우의 수, DFS로 풀면 이렇게 된다.

1.1 예제 케이스는 통과하나 코드 제출 시 시간 초과가 발생했다.

 

2. 칸 수에 따른 경우의 수를 1~5까지 비교해 본 결과 규칙이 있는 것을 알 수 있었다.

ex) 1칸 - 1개

      2칸 - 2개

      3칸 - 3개

      4칸 - 5개

      5칸 - 8개

=> n칸 = n-1칸의 경우의 수 + n-2칸의 경우의 수. 즉, 피보나치 수열의 형태를 하고 있다.

 

2-1. 위에서 나온 식을 이용하여 반복문을 사용하여 vector에 결과를 기록하고 해당 번호의 수를 나머지 연산을 통해 반환하면 된다.

 

코드

#include <vector>

using namespace std;

long long solution(int n)
{
    // 한 번에 1칸 혹은 2칸을 뛸 수 있다.
    // 칸이 총 1칸이면
    // 경우의 수는 1로 1개
    // 칸이 2칸이면
    // 경우의 수는 1-1, 2로 2개
    // 칸이 3칸이면
    // 경우의 수는 1-1-1, 1-2, 2-1 => 3개
    // 칸이 4칸이면
    // 경우의 수는 1-1-1-1, ... 예시와 동일 => 5개
    // 칸이 5칸이면
    // 경우의 수는 8개
    // 1-1-1-1-1
    // 1-1-1-2
    // 1-1-2-1
    // 1-2-1-1
    // 1-2-2
    // 2-1-1-1
    // 2-1-2
    // 2-2-1
    // 즉, f(n) = f(n - 2) + f(n - 1)가 되는 경향을 뛴다.
        
    vector<long long> Fibonazzi(n + 1);
    
    Fibonazzi[0] = 1;
    Fibonazzi[1] = 1;
    for(int IDX = 2; IDX <= n; ++IDX)
    {
        Fibonazzi[IDX] = (Fibonazzi[IDX - 2] + Fibonazzi[IDX -1]) % 1234567;
    }
    
    return Fibonazzi[n];
}