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

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐⭐ 
• 문제 유형: DP
• 사용 언어: 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 이하인 정수입니다.

---

💡 풀이 노트

조합(Combination)으로 접근

처음엔 이렇게 생각함

• 1칸만 사용하는 경우 → `1 + 1 + 1 + 1` → 조합: `4! / (0! * 4!)`
• 1칸 2개 + 2칸 1개 → `1 + 1 + 2` → 조합: `3! / (2! * 1!)`
• 2칸 2개 → `2 + 2` → 조합: `2! / (2! * 0!)`

그래서 n을 기준으로 1과 2의 개수 조합을 모두 구하고, 그에 맞는 조합 수를 계산하는 방식으로 접근

 

문제

• 각 조합 수를 구하기 위해서는 팩토리얼 연산이 필수
• 하지만 `n`이 커지면, 예를 들어 `n = 1000` 같은 값에서는
  • `1000!`은 수치가 상상을 초월할 만큼 커지며,
  • 자바의 `long` 타입(`9,223,372,036,854,775,807` ≈ 9경)을 쉽게 넘어서 버림
• 즉, 오버플로우(overflow) 현상이 발생하고,
• 그 결과 정답은 잘못된 값으로 계산되며,
  테스트 케이스 중에서도 특히 3번 혹은 7번처럼 입력 값이 큰 케이스에서 실패

피보나치(Fibonacci)로 전환

• 어떤 칸에 도달하는 방법은
• 그 직전 칸까지 도달한 방법 수 + 두 칸 전까지 도달한 방법 수의 합
  → `f(n)=f(n−1)+f(n−2)`
  
  • `f(1) = 1` 
    → (1칸만 뛰기)
  • `f(2) = 2`
    → (1+1, 2)
  • `f(3) = f(2) + f(1) = 2 + 1 = 3`
    → `[1+1+1], [1+2], [2+1]`
  • `f(4) = f(3) + f(2) = 3 + 2 = 5`
    → `[1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2]`

---

🚀 코드 (Java)

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n + 2]; 
        fibo[1] = 1;
        fibo[2] = 2;

        for (int i = 3; i <= n; i++) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
        }

        return fibo[n];
    }
}

---

🖥 실행 결과

입력 & 출력

n	result
4	5
3	3

---

🔄 개선 가능성

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest