(C++) - 프로그래머스(연습문제) : 멀리 뛰기

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

코딩테스트 연습 - 멀리 뛰기

dp문제였습니다.

 

풀이방법

 1칸 또는 2칸을 뛰므로 n에 도착하기 위한 경우의 수 점화식은 다음과 같습니다.

 

D[n] = D[n-1] + D[n-2]

 

 

Code

#include <bits/stdc++.h>
#define MOD 1234567
using namespace std;
using ll = long long;

ll d[2001];

ll dp(int num){
    if(num < 0) return 0;
    if(!num) return 1;
    ll &ret = d[num];
    if(ret!=-1) return ret;
    ret = 0;
    ret += dp(num-1) % MOD + dp(num-2) % MOD;
    return ret % MOD;
}
ll solution(int n) {
    memset(d,-1,sizeof(d));
    return dp(n);
}