[99클럽 5기 코테 스터디 TIL 21일차] 피보나치 함수 (feat. 동적계획법)

1) 문제

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

 

 

2) 풀이

코드 설명:

1. DP 테이블 (dp[41][2]) 사용
   • dp[i][0] : fibonacci(i)를 호출했을 때 0이 출력된 횟수
   • dp[i][1] : fibonacci(i)를 호출했을 때 1이 출력된 횟수
2. fibonacciPrecompute() 함수로 DP 테이블 채우기
   • dp[0]과 dp[1]을 초기값으로 설정
   • dp[i]는 dp[i-1]과 dp[i-2] 값을 이용해 채움
3. 입력 처리 및 출력 최적화
   • 여러 테스트 케이스가 주어지므로 StringBuilder를 이용하여 최적화

import java.io.*;

public class Main {
    static int[][] dp = new int[41][2]; // 0과 1의 출력 횟수를 저장하는 DP 테이블
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        
        fibonacciPrecompute(); // DP 테이블 미리 채우기
        
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
        }
        
        System.out.print(sb);
    }
    
    static void fibonacciPrecompute() {
        dp[0][0] = 1; dp[0][1] = 0; // fibonacci(0) 호출 시 (0: 1번, 1: 0번)
        dp[1][0] = 0; dp[1][1] = 1; // fibonacci(1) 호출 시 (0: 0번, 1: 1번)
        
        for (int i = 2; i <= 40; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }
    }
}