[백준] 1003 - 피보나치 함수(재도전)

문제링크: 바로가기

#DP(다이나믹 프로그래밍)

피보나치 함수는 다양한 유형으로 백준 문제에 출제된다. 이전 재귀함수를 활용한 제일 기초적인 피보나치 함수는 풀어보았는데 이번 문제는 간단한 설명임에도 접근방법이 어려웠다.

결국 해결하지 못했지만, 다음 번엔 꼭 성공하리라 다짐하면서 간략한 복기를 해본다.

친절하게 피보나치 함수 코드를 제공해준다. 물론 본 문제를 내기 위한 참고설명일 뿐이지만.

피보나치 특성 상 재귀로 연산을 중복/반복하게 되는데 fibonacci(0)과 fibonacci(1)이 각각 몇 번씩 출력되는지를 구하면 된다. 앞선 타일링 문제에서 적용한 DP(다이나믹 프로그래밍)을 사용해야겠단 것은 알았으나 출력을 어떻게 잡아(catch)줘야할지 꼬인 실타래가 끝내 풀리지 않았다.

다수 블로그 풀이법을 봤고 클론 코딩을 쳐봤음에도 이해가 되지 않아 고구마 1000개 먹은 상태를 간신히 넘기고 블로그에 클론 코딩이라도 분석하자는 마음으로 간략한 후기를 남긴다.

코드부터 투척

import java.util.Scanner;

public class Fibonacci_1003 {
    //GG 블로그 코드
    //모르겠다...(다시 풀어보기)
    static int[] dp = new int[41];
    public int solution(int n) {
        if(n <= 1 || dp[n] != 0) {
            return dp[n];
        } else {
            return dp[n] = solution(n-1) + solution(n-2);
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        //T
        int t = sc.nextInt();
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            new Fibonacci_1003().solution(n);

            if(n == 0) {
                System.out.println(1 + " " + 0);
            } else if(n == 1) {
                System.out.println(0 + " " + 1);
            } else {
                System.out.println(dp[n-1] + " " + dp[n]);
            }

        }


    }
}

코드는 메서드 함수와 메인 부분으로 나뉜다. solution 메서드 부분부터 보자. dp[] 배열 선언 시 크기는 n의 최대값인 40보다 1 크게 설정해줬다. 이유는 배열의 index는 0부터 시작해서 그런 것 같다.? 

리뷰하다 보니 메서드 재귀함수는 일반적인 피보나치 수열 구하는 공식이라 (0)과 (1) 출력과 관계가 없는 것 같은데?..

하.. 좀 더 공부하고 다시 와야겠다.