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

---

짝수 홀수일는 나누고, 이진법 관련해서 푸는 문제인 줄 알았는데

동적 계획법을 이용하는 문제였다...

생각도 못했다....

 

이전에 풀었던 피보나치 수 문제와 같은 것이었다...

 

2025.03.11 - [IT/JAVA] - [프로그래머스 12945] [Java] 피보나치 수

[프로그래머스 12945] [Java] 피보나치 수

---

/*
효진이가 끝에 도달하는 방법이 몇 가지인지
여기에 1234567를 나눈 나머지를 리턴
n은 1 이상, 2000 이하
 */
/*
1 => 1

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

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

4 => 5 (2+3)
(1,1,1,1)
(1,2,1)
(1,1,2)
(2,1,1)
(2,2)

5 => 8  (3+5)
(1,1,1,1,1) 
(2,1,1,1)   
(1,2,1,1)
(1,1,2,1)
(1,1,1,2)   
(2,2,1)
(2,1,2)
(1,2,2)     
 */

public class 멀리뛰기 {
    public static long solution(int n) {
        long[] f = new long[n+2];
        f[1] = 1;
        f[2] = 2;
        
        if(n>2) {
            for (int i=3; i<n+1; i++) {
                f[i] = (f[i-2]+f[i-1]) % 1234567;
            }
        }

        return f[n];
    }

    public static void main(String[] args) {
        System.out.println(solution(4));
        System.out.println(solution(3));
        System.out.println(solution(1));
    }
}

 

✍🏼 배열의 크기를 n+2 로 한 이유는

long[] f = new long[n+2];

long[] f = new long[n+1]로 하게 되면

n=1일때, 배열의 크기는 2이므로

f[0], f[1] 만 존재하게 되어 

f[2]=2 행에서 런타임에러 ArrayIndexOutOfBoundsException이 발생한다.

 

if(n==1) return 1; 로 해줄 수 있지만

코드의 간결성을 위해 전자를 선택했다.

 

조건문을 추가해 메모리를 절약하는게 더 나았으려나....