백준_피보나치함수_(1003)_동적계획법(java)

피보나치 함수

1. 문제

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

N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

아래와 같은 생각까지는 잘 했는데..... 또륵

// 갯수를 더한다. 예를 들어

// f(4) = f(3) + f(2)

// f(4) = f(4,0) + f(4,1) = f(3,0) + f(3,1) + f(2,0) + f(2,1)

solution - 2) 위와 같은 아이디어로 다른 사람 풀이 참고하여 풀이

* 갯수 세는 것을 동적계획법을 사용한다. 

* 아예 피보나치는 사용하지 않음,,,,

import java.util.Scanner;
public class Main {
    static int[][] res = new int[41][2];
    public static void main(String[] args) {
        res[0][0] = 1;
        res[1][1] = 1;
        for(int i = 2; i < 41; i++) {
            for(int j = 0; j < 2; j++) {
                res[i][j] = res[i-1][j] + res[i-2][j];
            }
            
        }
 
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i < T; i++) {
                int n = sc.nextInt();
                System.out.println(res[n][0] + " " + res[n][1]);
        }
        
        
        sc.close();
    }
}

solution - 1) 시간초과

import java.util.Scanner;
 
public class Main {
    static int[] one = new int[41];
    static int[] two = new int[41];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i < T; i++) {
                int n = sc.nextInt();
                fibonacci(n,n);
                System.out.println(one[n] + " " + two[n]);
        }
        
        sc.close();
    }
 
    private static int fibonacci(int n, int now) {
        if (now == 0) {
            one[n]++;
            return 0;
        } else if (now == 1) {
            two[n]++;
            return 1;
        } else if (now == 2) {
            one[n]++;
            two[n]++;
            return 1;
        } else {
            return fibonacci(n, now-1) + fibonacci(n, now-2);
        }
    }
}