[Programmers] 멀리 뛰기

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
   
    
    int tmp=3;
    unsigned long long f[n+1];
    f[1]=1;
    f[2]=2;
    while(tmp<=n){
        f[tmp]=(f[tmp-1] + f[tmp-2])%1234567;
        tmp++;
    }
    
    return f[n];
}

피보나치 수열을 이용하였다.
n번째 칸에 도달하는 경우는
1. n-1 번째에서 1칸 뛰는 경우
2. n-2 번째에서 2칸 뛰는 경우
로 나뉘기 때문이다.

최근에 푼 거스름돈 문제와 달리 2차원 배열을 선언할 필요가 없는 게, 이 문제는 뛰는 칸수의 순서도 구분하여 횟수를 카운트 하기 때문인 것 같다.

n이 2000이하인 걸 보고 타입을 대충 했다가 계속 테스트 실패했다. 타입도 정교하게 쓰도록 노력하기.