lv2) 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

#include <string>
#include <vector>
#include<iostream>
using namespace std;
long long answer= 0;
void dfs(int sum, int lv, int limit){
    if(lv <= limit){
        if(sum == limit){
            answer++;
            return;
        }
        if(lv == limit)return;
    }
    if(sum == limit){
        answer++;
       return;     }
    if(sum > limit)return;
    for(int i = 1 ; i <=2;++i){
        dfs(sum + i, lv+1, limit);
    }
}
long long solution(int n) {

   // dfs(0, 0, n);   시간초과 
    //dp 점화식: dp[n] = dp[n-1] + dp[n-2];
   vector<long long>dp(n+1);
    if(n == 1)return 1;
    if(n == 2) return 2;
   dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
     for(int idx = 3; idx <= n ;++idx){
         dp[idx] = (dp[idx-1] + dp[idx-2]) % 1234567;
    }   
    
    return dp[n];
}

- dfs로 하면 시간 초과

- dp로 진행해야 하며, dp[idx] 저장 때마다 %1234567 진행해야함.

- 조건만 보면 리턴 시에만 %1234567 을 하라했는데, 그게 아니었다. 매 계산 저장 전 modular 연산을 통해 오버플로우 방지를 해야한다. long long 타입이어도 피보나치 수열의 값 범위를 온전히 담을 수 없기 때문이다.

 

피보나치 수열(이 문제의 점화식)은 n이 커질 수록 숫자가 기하급수적으로 증가한다.

• 제한 사항을 보면 n은 최대 2,000까지 주어진다.
• long long 타입이 아무리 큰 수를 담을 수 있다고 해도, 피보나치 수열의 90번째 항만 넘어가도 표현할 수 있는 범위를 초과해 버린다. 2,000번째 항은 상상할 수 없을 정도로 큰 수가 되어 쓰레기 값이 담기게 된다.