[프로그래머스/c++] Lv2 멀리 뛰기

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

프로그래머스

피보나치수열과 동일한 규칙이기 때문에 간단하게 dp로 푼다. 이것이 피보나치수열과 동일한 규칙인 것만 알면 푸는 것은 간단하다. 

 

이 문제가 피보나치수열과 동일한 규칙인 이유:

 

• 효진이가 마지막 칸에 도달하는 방법은 그 직전 칸(1칸) 또는 그 이전 칸(2칸)에서 한 번의 점프로 도달할 수 있음
• n번째 칸에 도달하는 방법의 수는 n-1번째 칸에 도달하는 방법의 수와 n-2번째 칸에 도달하는 방법의 수를 더한 것과 같다. 이는 피보나치 수열의 정의와 동일.
• 즉, dp[n] = dp[n-1] + dp[n-2]가 되는 것

이처럼 이전 두 칸에서 도달하는 방법을 더해 나가는 방식은 피보나치 수열과 동일한 규칙이기 때문에, 이 문제를 피보나치 방식으로 해결할 수 있다. 

 

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;

    int dp[2001];
    dp[1] = 1;
    dp[2] = 2;

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

        //메모리 초과 및 계산 시간 증가 방지
        dp[i] = dp[i] % 1234567;
    }
    answer = dp[n] % 1234567;
    return answer;
}

 

혹시나 나처럼 dp[i] = dp[i] % 1234567 하면 값 바뀌는거 아니야? 하는 사람들을 위해 모듈로 연산의 특징 때문에 그런거라고 하니까...정리도 따로 해놨습니다. 별건 아님..

https://hello-world-cpp.tistory.com/156