[백준]1003. 피보나치 함수 (java, python)

링크

피보나치 함수

문제 분석

• 기본적인 다이나믹 프로그래밍 문제입니다

f(N) = f(N - 1) + f(N - 2) 를 구현합니다

• N이 1일 때, 2일 때를 기저 조건으로 설정합니다

• 파이썬 코드는 타뷸레이션, 슬라이딩 윈도우로 해결했습니다
  • 이 전 두 개의 값만 알면 되기 때문에, a와 b만 유지하며 해결합니다

코드

JAVA

import java.util.Scanner;

public class Q1003 {
    static int[] cache;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        cache = new int[42];
        cache[0] = 0;
        cache[1] = 1;
        for(int t = 1; t <= tc; t++) {
            int n = sc.nextInt();
            if(n == 0)
                System.out.println("1 0");
            else
                System.out.println(fibo(n - 1) + " " + fibo(n));
        }
    }

    public static int fibo(int n) {
        if(n == 0 || n == 1) return cache[n];
        else if(cache[n] == 0)
            cache[n] =  fibo(n - 1) + fibo(n - 2);
        return cache[n];
    }
}

PYTHON

for i in range(int(input())):
    a, b = 1, 0
    for j in range(int(input())):
        a, b = b, a + b
    print(a, b)