프로그래머스 - 멀리 뛰기 문제 (자바)

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

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

피보나치 수열이나 점화식으로 풀수 있는 문제 인데 저는 점화식으로 풀었습니다.

dp[뛰어야하는 거리]로

dp[1] 1

dp[2] 11, 2

dp[3] 111, 12, 21

dp[4] 1111, 112, 211, 22, 121

 

dp[1]에 2를 더하는 방법인 11, 2를 추가해보면 111, 12가 나옵니다.

dp[2]에 1를 더하는 방법인 1를 추가해보면 111, 21가 나옵니다.

두 경우의 중복인 111를 하나 제외하면 111, 12, 21 -> dp[3]의 경우의 수가 됩니다.

 

dp[2]에 2를 더하는 방법인 11, 2를 추가해보면 1111, 112, 211, 22가 나옵니다.

dp[3]에 1를 더하는 방법인 1를 추가해보면 1111, 121, 211 가 나옵니다.

두 경우의 중복인 1111, 211 제외하면 1111, 112, 211, 22, 121 -> dp[4]의 경우의 수가 됩니다.

 

중복되는 경우는 dp[큰 값] - dp[작은 값] 만큼 중복됩니다.

 

이를 점화식으로 해보면 아래와 같습니다.

dp[i] = dp[i-2] * 2 + dp[i-1] - (dp[i-1] - dp[i-2])

 

마지막으로 dp에 저장할때 %1234567를 적용하여 int의 범위를 벗어나지 않게 해주면 됩니다.

// 프로그래머스 멀리 뛰기 문제
class Jump {
    static final int MOD = 1234567;
    public long solution(int n) {
        int[] dp = new int[2001];
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-2] * 2 + (dp[i-1] - dp[i-2])) % MOD;
        }
        return dp[n];
    }
}