99클럽 코테 스터디 2일차 TIL - 백준 14495번 : 피보나치 비스무리한 수열

항해99 클럽 코테 스터디 2일차 TIL - 자바 미들러 4/1 (화요일)

https://www.acmicpc.net/problem/14495

✅ 문제

📌  접근방법

처음엔 막연히 재귀함수를 이용하였지만 시간복잡도가 O(2^N)이라 시간 초과로 런타임 오류가 났다.

이를 해결하려면 메모이제이션(DP) 또는 반복문을 사용한 동적 계획법을 사용해야한다. -> O(N)

또한, 문제조건에서 n이 116까지 입력받는데 f(116)은 int의 범위를 넘기 때문에 long을 써야했다.

 

런타임 오류 (오답)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        System.out.println(pivo(n));
    }

    public static int pivo(int n) {

        if (n == 1 || n == 2 || n == 3) {
            return 1;
        }
        return pivo(n - 1) + pivo(n - 3);
    }
}

🔑 풀이

메모이제이션 (Top-down DP)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 99클럽 코딩스터디 Day2
public class Main {

    static long[] dp;

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

        dp = new long[n + 1]; // n까지 저장할 배열
        System.out.println(pivo(n));
    }

    public static long pivo(int n) {
        if (n == 1 || n == 2 || n == 3) return 1; // 기본값

        if (dp[n] != 0) return dp[n]; // 이미 계산된 값이면 반환

        return dp[n] = pivo(n - 1) + pivo(n - 3); // 값 저장 후 반환
    }
}

 

반복문 (Bottom-Up DP)

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());

        if (n == 1 || n == 2 || n == 3) {
            System.out.println(1);
            return;
        }

        long[] dp = new long[n + 1];
        dp[1] = dp[2] = dp[3] = 1; // 초기값 설정

        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 3]; // 점화식 적용
        }

        System.out.println(dp[n]);
    }
}

 

 

📝 TIL

---

Top-Down DP (메모이제이션) vs. Bottom-Up DP (반복문 DP)  

 

• 입력 크기가 작거나 재귀 구조가 자연스러울 때 : Top-Down DP
• 입력 크기가 크고 빠른 계산이 필요할 때 : Bottom-Up DP

큰 입력(n이 10^6이상)에서는 Bottom-Up DP가 더 안정적이고 빠르며 좋다.

 

실행 코드 (백준 페이지)

http://boj.kr/ed23a227d31947a1abbb4618581d449b