[ 프로그래머스 ] 12914 멀리 뛰기

Link | 12914번 문제 : 멀리 뛰기

📌 Analyze

DP로 간단하게 해결할 수 있는 문제이다.

n번째 칸에 도달할 수 있는 방법은 2가지이다.

n - 1번째 칸에서 1칸을 이동하거나 n - 2번째 칸에서 2칸을 이동하는 것이다.

이를 수식으로 나타내면 dp[n] = dp[n-1] + dp[n-2] 이다.

수식을 바탕으로 DP 알고리즘을 구현하면 된다.

다만, dp[1]과 dp[2]는 각각 1과 2로 초기화하고 입력값 n이 1일 때는 따로 처리해야 한다.

📌 Code

GitHub Repository

class Solution {
    public long solution(int n) {
        if (n == 1) return 1;
        else {
            int[] dp = new int[n + 1];
            dp[2] = (dp[1] = 1) + 1;
            for (int i = 3; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
            return dp[n];
        }
    }
}