[240420] 알고리즘 리부트 53일차 - 백준 2747 자바

1부터 n까지의 수를 오름차순 및 내림차순으로 출력하도록 재귀를 구현하자.

- 백준 2747 피보나치 수

위 문제는 중복 연산이 많기 때문에 메모이제이션을 활용해야만 시간 초과가 발생하지 않는다.

package BaekJoon.recursion;

import java.util.Scanner;

public class BJ2747 {
    public static int[] arr;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        arr = new int[n + 2];
        arr[0] = 0;
        arr[1] = 1;
        pibo(2, n);

        System.out.println(arr[n]);
    }

    private static void pibo(int num, int n) {
        if (num == n + 1) return;

        arr[num] = arr[num - 1] + arr[num - 2];
        pibo(num+1, n);
    }
}

package BaekJoon.recursion;

import java.util.Scanner;

public class BJ2747 {
    public static int[] arr;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        arr = new int[n + 2];

        System.out.println(fibo(n));
    }

    private static int fibo(int n) {
        if (n == 1 || n == 2) return 1;

        if (arr[n] != 0) return arr[n];

        arr[n] = fibo(n - 1) + fibo(n - 2);

        return arr[n];
    }
}