[Lv 2] 멀리 뛰기

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

프로그래머스

 

이 문제는 dp를 사용하면 해결할 수 있다.

n칸을 뛸 수 있는 경우의 수를 구하는 문제이므로

1칸을 뛸 수 있는 경우, 2칸을 뛸 수 있는 경우, 3칸을 뛸 수 있는 경우를 구하면

각각 1, 2, 3이 된다. 즉, dp[3] = dp[1] + dp[2]가 성립하는 것을 알 수 있다.

또한, 다른 방법으로 점화식을 구한다면 3칸을 뛸 수 있는 경우는 1칸과 2칸을 반드시 거쳐야하므로 각 경우를 더하면 알 수 있다.

 

#include <string>
#include <vector>
using namespace std;

long long dp[2001];

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