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

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

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

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

풀이

문제의 조건대로 n이 1일때부터 경우의 수를 구해보았다.

n	방법	경우의 수
n = 1	1	1
n = 2	1 + 1 2	2
n = 3	1 + 1 + 1 2 + 1 1 + 2	3
n = 4	1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 2 + 2	5

n이 4일때의 규칙을 보면 파란색으로 색칠한 부분은 n이 3일때의 방법에 + 1을 해준 값이고, 빨간색으로 색칠한 부분은 n이 2일때의 방법에 + 2를 해준 값이다.

 

즉 n(4) = n(3) + n(2)가 된다. 마찬가지로 n(3) = n(2) + n(1)이다. 이는 피보나치 함수와 같다.

 

피보나치함수를 다이내믹프로그래밍 방법으로 구해주면 된다. 이때 n == 1일때의 종료 조건이 없다면 시간초과가 발생하므로 이 부분을 주의해서 풀어야 한다.

 

코드

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