[c++/프로그래머스] 멀리 뛰기

문제 링크

멀리 뛰기

풀이

dq로 푸는 문제 (피보나치니까 아마도..)

1. 칸이 0개 있을 때는, 안 뛰는 경우의 수 1
   칸이 1개 있을 때는, 한 번 뛰는 경우의 수 1
2개 부터는, 0개 있을 때에서 한 번에 2번 점프하는 경우의 수랑, 1개 있을 때에서 한 번 점프하는 경우의 수를 더하면 된다는 아이디어(니까 다이나믹 프로그래밍이 맞겠지?)
   즉 점화식은 v[n] = v[n-1] + v[n-2]
2. 생각해보니 피보나치랑 똑같다.

코드

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    
    vector<int> v(n+1);
    
    v[0]=1; v[1]=1;
    for(int i=2;i<=n;i++)
    {
        v[i]=(v[i-1]+v[i-2])%1234567;
    }
    
    answer=v[n];
    
    
    return answer;
}