[BOJ][DP] 1003. 피보나치 함수 (java / python)

 

✏️ 문제

 

 

🔢 알고리즘

 

#DP  #다이나믹프로그래밍

 

 

🤯 풀이 방법

 

문제에서 재귀 함수, 출력 어쩌고 했다고 그대로 풀면 당연히 시간 초과가 난다.

0부터 테스트케이스를 보면,

0의 경우: 0 출력 후 리턴 <1, 0>

1의 경우: 1 출력 후 리턴 <0, 1>

2의 경우: call f(0), f(0) 이므로 f(0)의 출력 수와 f(1)의 출력 수를 더하면 <1, 1>

3의 경우: call f(1), f(2) -> (0, 1) + (1, 1) = <1, 2>

4의 경우: call f(2), f(3) -> (1, 1) + (1, 2) = <2, 3>

5의 경우: call f(3), f(4) -> (1, 2) + (2, 3) = <3, 5>

6의 경우: call f(4), f(5) -> (2, 3) + (3, 5) = <5, 8>

 

숫자의 나열이 익숙하다. 1, 1, 2, 3, 5, 8, ...

이렇게 0이 출력되는 횟수는 N-1번째 피보나치 숫자, 1이 출력되는 숫자는 N번째 피보나치 숫자가 된다.

이때 당연히 재귀로 피보나치를 구할 필요도 없다. 배열을 만들어서 이전 인덱스와 그 전 인덱스를 더해준다.

 

파이썬은 N의 맥시멈 값이 40인 걸 이용한 것 같은데 그때는 피보나치 숫자인 줄 모르고 0, 1 인덱스를 각각 가공했던 것 같다.

자바는 배열 하나를 전체에서 사용하고 매번 새로운 N이 나오면 그때 이전에 해놓은 값 다음부터 만들거나 이미 저장했던 값이면 그대로 쓰는 식으로 사용했다

 

 

👾 구현 코드 (자바)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> stock = new ArrayList<>();
        int max = 1;
        stock.add(0);
        stock.add(1);

        int T = Integer.parseInt(st.nextToken());
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            if (N != 0) {
            	// 테스트 케이스가 여러 개므로
                // 이미 계산해 둔 값을 쓰기 위해서
                // 여러 테스트케이스의 최신 값과 이전까지의 max값을 비교한다
                if (N > max) {
                    for (int m = max + 1; m <= N; m++) {
                        stock.add(stock.get(m - 2) + stock.get(m - 1));
                    }
                    max = N;
                }
                System.out.println(stock.get(N - 1) + " " + stock.get(N));

            } else {	// 0인 경우에는 N - 1 인덱스에서 오류가 나니 예외 처리
                System.out.println("1 0");
            }

        }
    }


}

 

 

👾 구현 코드 (파이썬)

T = int(input())
dp = [[1, 0], [0, 1]]
for i in range(2, 43):
    dp.append([dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]])

for tc in range(T):
    N = int(input())

    print(dp[N][0], dp[N][1])

 

 

 

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