프로그래머스 멀리 뛰기 (Level2 Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=java

프로그래머스

---

문제

문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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가지 방법으로 멀리 뛸 수 있습니다.

---

문제 해결을 위한 과정

이 문제는 작은 단위의 정답들이 모여 다음 큰 단위의 정답을 만드는 전형적인 동적 계획법(DP) 문제입니다. 직접 규칙을 써 내려가다 보면 익숙한 규칙을 발견할 수 있습니다.

• 1칸을 뛸 때 가짓수: 1 (1)
• 2칸을 뛸 때 가짓수: 2 (1+1, 2)
• 3칸을 뛸 때 가짓수: 3 (1+1+1, 1+2, 2+1)
• 4칸을 뛸 때 가짓수: 5

잘 보면 앞의 두 숫자를 더하면 다음 숫자가 되는 피보나치 수열의 형태를 띱니다. 즉, 점화식은 dp[i] = dp[i-1] + dp[i-2]가 됩니다.

1. 메모이제이션 배열 선언: 문제 조건에서 n은 최대 2,000까지 주어지므로 값을 저장할 dp 배열의 크기를 2001로 넉넉하게 잡아줍니다.
2. 초기값 설정: 1칸일 때의 방법 dp[1] = 1, 2칸일 때의 방법 dp[2] = 2를 먼저 채워줍니다.
3. 예외 처리: 만약 구하고자 하는 n이 1이거나 2라면 더 이상 계산할 필요 없이 초기값을 바로 반환합니다.
4. 반복문 수행 (Bottom-Up): 3부터 2,000까지 루프를 돌며 점화식에 맞게 배열을 채워나갑니다. 이때 값이 자료형 범위를 넘어가지 않도록 매번 1234567로 나눈 나머지를 저장합니다.

---

소스코드

import java.util.*;

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