멀리 뛰기 / 피보나치 수열 활용

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

 

처음에 이 문제를 접했을 때, 모든 경우의 수를 다 해봐야되나? 라고 생각이 들었는데 n값이 2000 이하인 정수라는 것을 보고 이 방법으로 접근하면 안된다고 생각했다.

하지만 도무지 다른 방법이 떠오르지 않아 '질문하기' 를 살펴보았는데 피보나치 수열로 해결할 수 있다는 글을 보고 피보나치 수열에 대해 조사하였다.

피보나치 수열

 

✅ 피보나치 수열로 문제 해결

#include <string>
#include <vector>

using namespace std;

long long solution(int n) 
{
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i = 3; i <= n; ++i)
    {
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }
    
    long long answer = dp[n];
    
    return answer;
}

• 목적지까지 1칸이라면, 경우의 수는 한 칸 뛰기로 답은 1이 된다.
• 목적지까지 2칸이라면, 한 칸 뛰기를 두 번하는 경우와 두 칸 뛰기를 한 번해서 가는 경우로 답은 2가 된다.
• 목적지까지 3칸이라면, 목적지의 2칸 뒤에서 두 칸 뛰기를 하는 경우와 목적지의 1칸 뒤에서 한 칸 뛰기를 하는 경우 두 가지가 된다. 
• 앞에서 목적지까지 2칸인 상황에서 2가지의 경우인 것을 확인했고, 목적지까지 1칸인 상황에서 1가지의 경우인 것을 확인했기 때문에, 목적지까지 3칸이라면 2 + 1로 답은 3이된다.
• 이 매커니즘을 반복하면 목적지 n까지의 경우의 수는 n - 2와 n - 1의 경우의 수를 합친 것과 같다.
  F[n] = F[n - 1] + F[n - 2] 

 

📍 배열을 쓰지 않는다면?

#include <string>
#include <vector>

using namespace std;

long long solution(int n) 
{
    if(n == 1) return 1;
    if(n == 2) return 2;
    
    int pprev = 1;
    int prev = 2;
    int current;
    
    for(int i = 3; i <= n; ++i)
    {
        current = (pprev + prev) % 1234567;
        pprev = prev;
        prev = current;
    }
    
    return current;
}

현재 문제에서 n 값이 2000 이하의 정수라고 되어있지만
만약 아주 큰 수라면 큰 공간복잡도를 가지게 될 것이다. 배열을 사용하지 않고 변수로도 충분히 로직을 구현할 수 있었다.