[ 프로그래머스 / 멀리뛰기] (자바)

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

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

 

 

계단을 오른다.... (1칸, 2칸) or 멀리뛰기를 한다... (1칸, 2칸) 등은 모두 dp를 사용한다.

전형적인 문제이다. 반복적인 조합을 이용해서 최선의 결과를 찾아야 하는 것이다.

여기서는 1칸,2칸만 사용이 가능하다. 따라서 1칸과 2칸만을 이용한다.

 

가장 먼저 초기화를 해준다.

dp[1]과 dp[2]를 해준다. 그렇다면 그 이후에는 이 2개만을 이용해서 만들면 된다.

즉, 점화식은 dp[n] = dp[n-1] + dp[n-2]의 형식이다.

 

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