[C++] 멀리 뛰기

[문제]

코딩테스트 연습 - 멀리 뛰기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

2칸 혹은 1칸을 움직일 수 있으니 간단하게 생각해서 3칸을 움직일 수 있는 경우는 1칸째에서 2칸을 한번에 움직이는 경우 + 2칸째에서 1칸을 추가로 오는 경우이다.

즉, dp[i] = dp[i - 1] + dp[i - 2] 라는 점화식이 완성이 되니 이를 이용해서 풀자.

[회고]

이전엔 DP에 대한 이해도가 부족해서 어떻게 접근하는지 헷갈렸었는데 이제는 확실히 계단 뛰어오르기 정도는 익숙해진 것 같다.

뿌듯!

[코드]

#include <string>
#include <vector>

using namespace std;

int dp[2002];

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