[백준/Java] 1003 - 피보나치 함수

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

문제

---

풀이

처음에는 그냥 단순히 피보나치를 재귀로 호출하면서 0이나 1이 나올 때 카운트를 증가하였다

당연하게도 시간초과가 났다

 

도저히 풀이 방법이 안떠올라서 Stranger's LAB 님의 풀이 방식을 참고하였다

이미 구한 겂을 재사용하기 위해 DP를 활용한다

한 번 탐색할 때마다 N의 0과 1의 값을 저장해두고 이후 다음 탐색에서 이미 탐색했던 노드라면 해당 값을 사용한다

 

dp라는 2차원 배열을 생성하고 탐색하지 않은 N에 대한 0, 1 값을 dp에 저장하면서 재귀 호출을 해준다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static Integer[][] dp = new Integer[41][2];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        dp[0][0] = 1;   // N=0 일 때 0 호출 횟수
        dp[0][1] = 0;   // N=0 일 때 1 호출 횟수
        dp[1][0] = 0;   // N=1 일 때 0 호출 횟수
        dp[1][1] = 1;   // N=1 일 때 1 호출 횟수
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            fibo(N);
            sb.append(dp[N][0] + " " + dp[N][1]).append("\n");
        }

        System.out.println(sb);
    }

    static Integer[] fibo(int N) {
        // N에 대한 0, 1의 호출 횟수가 없을 때(탐색하지 않은 값)
        if (dp[N][0] == null || dp[N][1] == null) {
            // 각 N에 대한 0, 1 호출 횟수를 재귀호출
            dp[N][0] = fibo(N - 1)[0] + fibo(N - 2)[0];
            dp[N][1] = fibo(N - 1)[1] + fibo(N - 2)[1];
        }
        // [N][0], [N][1]을 담고 있는 [N]을 반환
        return dp[N];
    }
}

결과