프로그래머스(C++) - 멀리뛰기

●문제

●입출력

 

문제해석

n숫자값만큼 1칸 or 2칸 이동하여 총 n 숫자칸 만큼 이동할수있는 경우의수를 구하고 1234567를 나눈값을 리턴

 

푼방법

결국 n - 1 과 n -2 수치를 더한 값을 계산하게된다 이는 곧

점화식이 피보나치 수열의 점화식과 같다는걸 의미한다

#include <string>
#include <vector>

using namespace std;

vector<long long>mmn;
long long solution(int n) 
{
    const int insertNum = 1234567;

    if (mmn.size() <= n)
        mmn = vector<long long>(n + 1, -1);

    if (n <= 1)
        return 1;

    if (mmn[n] != -1)
        return mmn[n];

    mmn[n] = (solution(n - 1) + solution(n - 2)) % insertNum;
    return mmn[n];

}

 

레벨 : 2

점수 : 4