[프로그래머스] 2단계 - 멀리뛰기

문제 설명

멀리뛰기를 할 때 한번에 1칸, 2칸만 뛸 수 있을때 n칸이 주어졌을때 뛸 수 있는 경우의 수를 return

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

프로그래머스

 

문제 풀이법

문제를 처음 봤을때 DP 문제인지 모르고 조합으로 풀어야하나..? 한번에 뛸 수 있는 칸의 크기에 초점을 두어서 문제를 보고 있었다

하지만 정답을 1234567로 나누어서 return 하라는 문구를 보고 이전에 비슷하게 return 문구가 있던 피보나치 수열을 생각하게되었고, 그 피보나치 수열 문제를 풀었던 코드를 활용하여 이번 문제도 풀게되었다

 

이 문제는 DP 문제였고 점화식이 피보나치 수열과 거의 비슷했다 

f(0) = 0, f(0) = 1일때 f(n) = f(n - 1) + f(n - 2)의 점화식을 그대로 차용해 return만 f(n + 1)로 해주었다

 

이때 벡터에 값을 1234567로 나눈 값을 넣어주지 않는다면 자료형의 범위를 넘어갈 것이기 때문에 1234567을 나누어주면서 값을 저장해주어야 한다

 

피보나치 수열의 점화식을 사용하지 않는다면

f(1) = 1, f(2) = 2 일때 f(n) = f(n - 1) + f(n - 2)를 한 후에 f(n)을 return 해주면 된다

 

문제를 보고 이 문제를 어떻게 풀어가야할지 알아내기 위해 많이 연습해야겠다 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

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