---

문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항
n은 1 이상, 2000 이하인 정수입니다.
입출력 예

n	result
4	5
3	3

입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

---

풀이

동적계획법을 이용하여 풀었다

어째서 dp라고 생각 할 수 있을까?


1. 중복되는 부분 문제가 존재하는가
큰 문제를 작은 부분 문제들로 나눌 수 있고, 이 작은 부분 문제들이 여러 번 반복되는가?
2. 최적 부분 구조가 존재하는가
작은 부분 문제들의 최적해를 이용하여 전체 문제의 최적해를 찾을 수 있는가?

1칸   => 1가지
2칸   => 2가지
3칸   => 3가지 = 1칸 결과 + 2칸 결과
4칸   => 5가지 = 2칸 결과 + 3칸 결과
5칸   => 3칸 결과 + 4칸 결과

피보나치 수열과 같다
이 경우 result[i] = result[i-1] + result[i-2] 로 진행하면된다

1. dp를 구현하기 위해 각 단계의 결과를 담을 배열을 구성한다

  int dp[2001] = {0}; // n이 최대 2000이므로 배열 크기를 2001로 설정

2. 최소한 2번까지는 있어야 하기때문에 초기값을 설정한다

  dp[1] = 1;
  dp[2] = 2;

3. 동적계획법을 사용하여 배열을 채워나간다

for (int i = 3; i <= n; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

4. 반환 할 값을 설정한다

return dp[n];
//n은 문제에서 인풋으로 주어지는 값

전체코드(cpp)

#include <iostream>
#include <vector>

using namespace std;

int 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;
    }
    return dp[n];
}

int main() {
    // 예시 입력과 출력
    cout << solution(4) << endl; // 5
    cout << solution(3) << endl; // 3

    return 0;
}