[프로그래머스] 프로그래머스 Level3 멀리 뛰기 C++

문제

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

코딩테스트 연습 - 멀리 뛰기

풀이

DP로 해결할 수 있었다. 이 문제도 2 x n 타일링처럼 점화식만 구해주면 레벨3 치고는 그렇게 어렵지 않다.

DP[N]이 N칸을 뛰어야 할 때 나올 수 있는 경우의 수라고 가정하면 점화식은 DP[N] = DP[N - 1] + DP[N - 2]이다.

점화식 도출 과정은 예를들어 N = 5라고 가정하자 DP[5]는 DP[4]에서 1칸만 더 뛰면 되는 것이고, DP[3]에서 2칸만 더 뛰면 된다. 즉 DP[5] = DP[4] + DP[3]임을 알 수 있는 것이다.

 

코드

#include <string>
#include <vector>
#define MOD 1234567

using namespace std;

long long dp[60001];

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

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

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

    answer = dp[n];

    return answer;
}