[프로그래머스 lv2] 멀리 뛰기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

대표적인 dp 유형이다.

효진이가 n번째 칸에 도달할 때, 다음과 같은 두가지 방법이 가능하다.

 

1. n-1번째 칸까지 뛰고 마지막 한칸을 뛰어 n번째 칸에 도달하는 방법

2. n-2번째 칸까지 뛰고 마지막에 두칸을 뛰어 n번째 칸에 도달하는 방법

 

따라서, dp[n]을 n번째 칸까지 뛰는 경우의 수라고 할 때,

dp[n] = dp[n-1](n-1번쨰 칸까지 도달하는 경우의 수) + dp[n-2](n-2번째 칸까지 도달하는 경우의 수)로 점화식을 세울 수 있다.

 

초항 dp[1] = 1, dp[2] = 2를 설정해주고, dp[i]를 구할 때마다 1234567로 나눈 나머지를 저장한다.

이후, dp[n]을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

long long solution(int n) {
    
    long long dp[2005] = {0};
    
    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];
}