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

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

n은 1 이상, 2000 이하인 정수입니다.

입출력 예
n result
4 5
3 3

입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

---

👉 풀이과정

1칸 또는 2칸을 뛸 수 있다는 내용을 보고 DP를 떠올렸다.

다른 분들은 조합이나 피보나치로 문제를 푸신 것 같은데...

어떤게 정답인지는 모르겠다..!

 

n이 1일때,

1 => 1번(1)

 

n이 2일때,

1 => 1번(1,1) 

2 => 1번(2) 

 

n이 3일때,

1 => 1번(1,1,1) 

1,2 => 2번(1,2) (2,1)

 

n이 4일때,

1 => 1번(1,1,1,1) 

1,2 => 2번(1,1,2) (1,2,1)(2,1,1)

2 => 2번(2,2)

 

n이 5일때,

1 => 1번(1,1,1,1,1) 

1,2 => 4번(1,1,1,2) (1,1,2,1)(1,2,1,1)(2,1,1,1)

2 => 3번(1,2,2)(2,1,2)(2,2,1)

 

1 -> 2 -> 3 -> 5 -> 8

 

즉, dp[n] = dp[n-1] + dp[n-2] 라고 할 수 있다!

 

📌 제출코드

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