[Algorithm] Programmers_멀리 뛰기 in Java

💡 Programmers Level 2. 멀리 뛰기:

1칸 또는 2칸을 뛰어 N칸까지 도달하는 총 경우의 수 구하기

🌱 코드 in Java

알고리즘: Dynamic Programming

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

처음에 재귀로 접근했다가, 시간 초과를 거하게 처맞고 고민했으나 접근 방법이 보이지 않아 찾아보니 DP로 해결할 수 있다해서
DP적 해결 방법을 고민해보았다.

이 문제에서 '1칸, 또는 2칸'을 뛸 수 있다는 문장에서 DP를 떠올릴 수 있다는데 다들 대단해..

1칸 -> 1개의 경우 2칸 -> 2개의 경우이고, 그 이후부터는 앞 경우의 수의 누적합이었다.

🧠 기억하자

1. 모듈러 연산은 총 합에 대한 모듈러 연산이나, 개별 합에 대한 모듈러 연산이나 결과가 같다.

• 분배의 법칙에 따라 그렇다