(Java) 백준 1003 - 피보나치 함수

문제 설명에 C++ 코드가 있길래 C++ 전용 문제인 줄 알고 안 풀었었다.

근데 해결한 사람들이 많은 문제여서 다시 보니 그냥 피보나치 함수 변형이었다.

F(0)과 F(1) 호출을 횟수를 세면 되는 문제이다.

처음에 아무 생각 없이 똑같이 재귀로 구현하고 시간 초과로 틀렸다.

연습장에 F(2), F(3) ... 호출 횟수를 몇 번 써보니 결국 DP라는 것을 알게 돼서 해결했다.

2차원 배열로 0이 호출된 횟수와 1이 호출된 횟수를 저장했다.

 

최종 코드

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

public class Main {
    static int t;
    static int[][] dp;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            dp(Integer.parseInt(br.readLine()));
        }
        System.out.println(sb);
    }

    public static StringBuilder dp(int num) {
        dp = new int[num + 2][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        for (int i = 2; i <= num; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }
        return sb.append(dp[num][0]).append(" ").append(dp[num][1]).append("\n");
    }
}