[프로그래머스] 멀리 뛰기 c++ (dp, 코드 및 설명)

문제 링크

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

프로그래머스

 

개념

이 문제를 역으로 생각을 해보면 예를 들어 우리는 10칸에 도달하려고하면 -> 8칸에서 두칸뛴것과 9칸에서 1칸을 뛴것을 생각하실 수 있습니다.

 

이것을 계속 반복하게 되서 처음으로 돌아가게 된다면 1칸과 2칸을 알게 된다면 모든 뒤 칸을 알 수 있습니다.

 

하지만 우리가 만약 

return f(n) = f(n-1) + f(n-2);

이런식의 재귀로 호출을 하게 된다면 얼마나 오랜 시간이 걸리게 될까?

 

재귀

2000으로 예시를 들게 되면 우리는 약 2^1999이라는 어마무시한 계산이 될것입니다.

dp

우리는 f(n) = f(n-1) + f(n-2)를 알게 되었기 때문에 

위의 사진처럼 진행을 하면 됩니다.

 

코드

/*

멀리뛰기 연습

1칸 또는 2칸을 뛸 수 있다는 것의 조합 -> 무조건 dp문제인듯 하다

사유 : dp로 인해 그 전에 dp[i] = dp[i-1] + dp[i -2] 이기 때문이다.

    그리고 n은 2000이하라는 제한사항을 보게 되면 역시 그럼을 다시 알 수 있다.

주의 사항 : 1234567을 나눈 나머지를 리턴한다는 점.

*/

#include <string>

#include <vector>

using namespace std;

long long solution(int n) {

    long long answer = 0;

   

    if(n == 1)

        return 1;

    else if(n == 2)

        return 2;

   

    vector<int> v(n,0); //백터의 n크기를 0으로 일단 셋팅

    v[0] = 1,v[1] = 2; //dp는 초기를 셋팅후 진행

   

    for(int i =2; i < n; i ++){

        v[i] = (v[i-1] + v[i - 2]) % 1234567;

    }

   

    answer = v.back();

   

   

    return answer;

}