[백준] 14495번: 피보나치 비스무리한 수열 (Java)

1 . 문제 설명

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다.

f(1) = f(2) = f(3) = 1 이며 나열하면 → 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, …

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구한다.

자연수 n: 1 ≤ n ≤ 116
시간 제한: 2초
메모리 제한: 512MB

2. 접근 방식

동적 계획법(DP) 방식을 사용한다.
dp 배열 (long[] dp)을 사용하여 초기값(1, 2, 3번째는 1)을 설정한 후,
점화식(f(n) = f(n-1) + f(n-3)) 기반으로 n번째까지 수를 구하고, 출력한다.

3. 틀린 이유 설명

백준 제출 시 “런타임 에러” 발샘

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 자연수 n

        long[] dp = new long[n+1];
        dp[1] = 1; dp[2] = 1; dp[3] = 1; // 1,2,3번째 1로 초기화

        // f(n) = f(n-1) + f(n-3);
        if (n > 3) {
            for (int i = 4; i <= n; i++) { // 1부터 n까지 피보나치 수열 구함
                dp[i] = dp[i-1] + dp[i-3];
            }
        }

        System.out.println(dp[n]); // n번째 피보나치 수 출력
    }
}

4. 올바른 접근 방식 및 해결 방식

long[] dp = new long[n+1]; → 배열 선언 부분에서 배열 크기를 n+1로 설정했다.

만약 n이 1일 경우 dp[3] = 1;에서 에러가 발생할 것이고, n이 2일 경우 for문에서 int i = 4;로 시작하기 때문에 에러가 발생할 것이다.

따라서 선언 부분에서 크기를 117로 고정해야 한다. (문제에서 자연수 n(1 ≤ n ≤ 116)이 주어지기 때문)

5. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 자연수 n

        long[] dp = new long[117];
        dp[1] = 1; dp[2] = 1; dp[3] = 1; // 1,2,3번째 1로 초기화

        // f(n) = f(n-1) + f(n-3);
        if (n > 3) {
            for (int i = 4; i <= n; i++) { // 1부터 n까지 피보나치 수열 구함
                dp[i] = dp[i-1] + dp[i-3];
            }
        }

        System.out.println(dp[n]); // n번째 피보나치 수 출력
    }
}

시간복잡도: $O(N)$

6. 분석 및 참고사항

DP 배열을 사용하는 경우 배열 크기에 대해 동적 할당할지, 정적 할당할지 고려해야 한다.
피보나치 수열과 같은 문제는 수가 굉장히 커지기 때문에 자료형(int, long 등)을 고려해야 한다.

boolean isGrowing = true;