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

• 프로그래머스 문제 URL

---

문제 요약

정수 n이 주어질 때, 1칸 또는 2칸씩만 뛸 수 있다고 하면 도착 지점까지 갈 수 있는 경우의 수를 구하는 문제다.
정답은 매우 커질 수 있으므로 1234567로 나눈 나머지를 반환한다.

---

핵심 아이디어

n칸에 도착하는 방법은 마지막 이동 기준으로 딱 두 가지뿐이다.

• n-1칸에서 1칸 뛰어서 도착
• n-2칸에서 2칸 뛰어서 도착

즉, n칸의 경우의 수는 n-1칸 경우의 수 + n-2칸 경우의 수로 표현되고, 이 구조가 피보나치 형태라 DP로 누적 계산하면 된다.

---

DP 정의 & 점화식

dp 정의

• arr[i] = i칸에 도착하는 경우의 수

초기값

• arr[1] = 1 (1칸: 1만 가능)
• arr[2] = 2 (2칸: 1+1, 2)

코드에서 n==1, n==2를 먼저 리턴하는 것도 안전한 예외 처리다.

점화식

• arr[i] = arr[i-1] + arr[i-2]

단, 값이 커지므로 매 단계에서 모듈러 연산을 적용한다.

arr[i] = (arr[i-1] % 1234567 + arr[i-2] % 1234567) % 1234567;

---

왜 매번 %를 해주나?

n이 커지면 경우의 수는 급격히 증가해서 int 범위를 넘어갈 수 있다.
그래서 문제에서 요구한 것처럼 “나머지”만 유지하도록 매 단계에 1234567로 모듈러를 적용해 오버플로우 위험을 줄인다.

(참고로 (a+b)%m = (a%m + b%m)%m 성질 때문에 이렇게 중간중간 나눠도 최종 나머지는 동일하다.)

---

전체 코드(제출용)

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

        if (n == 1) return 1;
        if (n == 2) return 2;

        arr[1] = 1;
        arr[2] = 2;

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

        long answer = arr[n];
        return answer;
    }
}