🏆 백준 14495 : 피보나치 비스무리한 수열

피보나치 비스무리한 수열📕

📌 문제 설명

기존 피보나치 수열에서 다음과 같이 변형된 수열을 구하는 문제입니다.

• 점화식: 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(1 ≤ N ≤ 116)이 주어질 때, f(N)을 구하는 문제입니다.

---

💡 접근 방법

1️⃣ 재귀 방식 (시간 초과)

처음에는 단순히 재귀를 이용하여 문제를 해결하려 했습니다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    System.out.println(fibo(N));
}

public static long fibo(int N) {
    if (N == 1 || N == 2 || N == 3) return 1;
    return fibo(N-1) + fibo(N-3);
}

하지만 N이 커질수록 같은 값을 여러 번 계산하게 되어 시간 초과가 발생했습니다.

2️⃣ 메모이제이션 적용

이 문제를 해결하기 위해 메모이제이션 (DP) 를 적용했습니다.

class Main{
    static long[] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        memo = new int[117];
        System.out.println(fibo(N));
    }

    public static int fibo(int N){
        if (N <= 0) return 0;
        if (N == 1 || N == 2 || N == 3) return memo[N] = 1;
        if (memo[N] != 0) return memo[N];

        return memo[N] = fibo(N-1) + fibo(N-3);
    }
}

하지만 여전히 틀렸습니다 판정을 받았습니다.

3️⃣ int → long 변경 후 해결

입력 범위가 1 ≤ N ≤ 116 이므로, f(N) 값이 매우 커질 가능성이 있습니다 그리고, 실제로 f(50)만 해도 15억이 넘어서 int 범위를 초과 합니다.

이를 해결하기 위해 int → long으로 변경을 했습니다.

class Main{
    static long[] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        memo = new long[117];
        System.out.println(fibo(N));
    }

    public static long fibo(int N){
        if (N <= 0) return 0;
        if (N == 1 || N == 2 || N == 3) return memo[N] = 1;
        if (memo[N] != 0) return memo[N];

        return memo[N] = fibo(N-1) + fibo(N-3);
    }
}

제출 후 드디어 정답 을 받았습니다. 🎉

---

🧐 회고

• 입력 데이터의 범위를 정확하게 분석하는 것이 중요하다는 것을 다시 한번 깨달았습니다.
• int와 long의 범위를 고려하지 않으면, 예상치 못한 오버플로우 문제로 인해 오답이 발생할 수 있다는 사실도 다시 한 번 느꼈습니다.