[Programmers] 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=cpp

프로그래머스

 
문제 조건을 보면 다음과 같습니다.
 
1. 효진이는 한 번에 한 칸 혹은 두 칸을 갈 수 있습니다.
2. 그렇다면 효진이가 0번째 칸에서 시작해 n번째 칸까지 간다면 몇 가지의 방법으로 갈 수 있는지를 출력해야 합니다.
 
이 문제를 읽어보자마자 예전에 백준에서 풀었던 숨바꼭질 시리즈, 1로 만들기 문제들이 생각이 났습니다.
사실 이 문제는 DP로 풀 수 있습니다. 
 
일단 DP[k] = k 번째 칸까지 이동하는 방법의 개수라고 합시다. 그러면 k칸으로 도착하기 전에 도달했던 칸은 어디일까요?
바로 k-1칸과 k-2칸이 됩니다. 그렇다면 DP[k] = k-1칸까지 간 다음 한 칸 뛰어서 온 경우의 수 + k-2칸까지 간 다음 두 칸 뛰어서 온 경우의 수 = DP[k-1] + DP[k-2] 꼴이 됩니다.
 
그러면 이제 우리는 다음과 같이 점화식을 세울 수 있습니다.
 

• 점화식 : DP[k] = DP[k-1] + DP[k-2] (for k > 2)
• 초기값 : DP[1] = DP[2] = 1

 
이를 기반으로 이제 코드만 짜면 되겠죠? 실제 코드는 다음과 같습니다. DP[3]부터 DP[n]까지 한 번씩만 보면 되므로 시간복잡도는 O(n)이 됩니다.
 

#include <bits/stdc++.h>
#define ll long long

using namespace std;

long long solution(int n) {
    long long answer = 0;
    vector<ll> v(n+1, 0);
    v[1] = 1, v[2] = 1;
    for(int i =1; i<=n; ++i){
        if(i+1 <= n) v[i+1] = (v[i+1]+v[i])%1234567;
        if(i+2 <= n) v[i+2] = (v[i+2]+v[i])%1234567;
    }
    answer = v[n];
    return answer;
}

 
이 문제도 예전에 풀었던 문제였는데... 예전에는 너무 이상하고 더 어렵게 풀었어서 다시 풀었습니다. 예전에는 한 번 뛴 횟수와 두 번 뛴 횟수가 정해지면 팩토리얼의 형태로 방법의 수를 계산할 수 있으니 한 번 뛴 횟수와 두 번 뛴 횟수를 계속 조정해가면서 풀었네요;;; 다만 저 문제를 풀었을 때가 2021년 11월, 제대로 PS를 해본 적이 없었던 때라서 그런지 오히려 제가 더 성장함을 느껴 뿌듯했습니다. (만약에 제가 2023년에 저 어지러운 방법으로 풀었다면 매우 반성했을 겁니다.)

+) 이 글 올리고나서 저 점화식을 다시 보니 피보나치 수열 점화식이었네요;;; 어쩐지 낯이 익다 했습니다.