멀리 뛰기

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

몇번 접한 유형의 문제이다.
이거
1. DFS로 풀었을때 :: 시간초과

#include <string>
#include <vector>

using namespace std;

long long answer = 0;

void dfs(int len, int sum){
    if(sum > len) return;
    
    if(sum == len){
        answer++;
        return;
    }
    
    dfs(len, sum + 1);
    dfs(len, sum + 2);
}

long long solution(int n) {
    long long rem = 1234567;
    dfs(n, 0);
    return answer % rem;
}

2. DP로 풀었을 때 :: 합격

#include <string>
#include <vector>

using namespace std;
long long dp[2001] = {0,};

long long solution(int n) {
    long long answer = 0;
    dp[1]=1;//1만들기
    dp[2]=2;//1 1또는 2
    for(int i=3; i<=n; i++)
    {
        dp[i]=(dp[i-1]+dp[i-2])%1234567;
    }
    
    answer = dp[n];
    
    return answer;
}

비슷한 유형 몇번 접했는데, DFS 아닌 DP로 접근하도록 노력해보자.