[220802][반스][인프런](7-4) 피보나치 재귀

[ffinn92]

📌 문제

⭐️ 아이디어

• if, else 구조로 만들고 DFS(n) 함수안에서 n + DFS(n) 구조로 만들어보자.

🤔 고민한 내용

• 1, 1, 2, 3, 5, 8이 아닌 1, 2, 4, 8, 16처럼 2배가된다. 이전 수를 더하려면 어떤식으로 짜야하는걸까?

💪 새롭게 배운 내용

- DFS 탐색과정에서 배열에 담아, 배열을 바로 출력해버려 시간을 줄일수 있구나

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

• DFS 구조를 한번에 생각해내는게 너무 어렵다.

✅ 본인 풀이

🏋️‍♀️ 시도횟수 : 회 | ⏱ 걸린시간 : ms | 💾 메모리 : MB

import java.io.IOException;
import java.util.Scanner;

public class If704FibonacciNumbers {
    static int[] fibo;

    public int DFS(int input) {
        if(fibo[input] > 0) {
            return fibo[input];
        }
        if (input == 1) {
            return fibo[input] = 1;
        } else if (input == 2) {
            return fibo[input] = 1;
        } else {
            return fibo[input] = DFS(input - 2) + DFS(input - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        If704FibonacciNumbers T = new If704FibonacciNumbers();
        Scanner sc = new Scanner(System.in);

        int input = sc.nextInt();
        fibo = new int[input + 1];
        T.DFS(input);
        for (int i = 1; i < input + 1; i++) {
            System.out.print(fibo[i] + " ");
        }
    }
}

참고한 자료

• 링크