인프런 커뮤니티 질문&답변

안녕하세요^^

이 문제는 피보나치 수열의 각 항을 매번 재귀를 호출해서 구하면 시간초과로 통과되지 않게 되어 있습니다.

영상의 방법으로 해야 시간초과가 나지 않습니다.

이 문제를 재귀로 통과하고 싶으면 메모이제이션 기법을 사용해야 합니다. 초보자에게는 약간 어려울 수 있습니다. 주로 top - down 다이나믹 기법에 사용합니다. 아래 코드는 위 코드에 메모이제이션을 사용한 코드입니다. 한 번 분석해보세요.

import java.util.Scanner;

public class Main {
    public static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	memo = new int[n];
        Main main = new Main();
        for (int i = 0; i < n; i++) {
            System.out.print(main.solution(i) + " ");
        }
    }

    private int solution(int i) {
	if(memo[i] > 0) return memo[i];
        if (i <= 1) {
            return 1;
        }
        return memo[i] = solution(i - 1) + solution(i - 2);
    }
}