✨ 문제

1003번-피보나치 함수
👉🏻 문제가 길어 한 화면에 안 담긴다..

알고리즘

dynamic programming(dp) 알고리즘

✨ 풀이

• 피보나치 수열 문제는 dp 문제로 워낙 유명하니..!
  👉🏻 근데 이 문제는 보통의 피보나치 수열과 약간 다르게, 문제에서 주어진 소스 코드에서 0과 1이 몇 번이나 나타나는지 구하는 것이다.
  👉🏻 하지만 이 또한 항상 같은 값을 가지는 작은 문제로 쪼개진다는 점!

• 문제에서 주어진 함수를 보면 0과 1은 각자 자기 자신이 리턴된다.

• 나머지 2~n은 재귀함수 형태로 매개변수로 n-1, n-2가 전달된다.
  👉🏻 이때 3을 함수 매개변수로 전달하면 리턴되는 fibonacci(2) + fibonacci(1)를 예시로 보자!
  ✔️ fibonacci(2)는 fibonacci(1) + fibonacci(0)이 리턴되고, 여기서 fibonacci(1)은 1이, fibonacci(0)은 0이 리턴되어 fibonacci(2)는 결국 1 + 0 = 2가 된다.
  ✔️ fibonacci(1)은 1이 리턴된다.
  ✔️ 총 2 + 1 = 3이 결과값이 된다.
  👉🏻 fibonacci(1) 계산을 2번 수행하게 된다. 3을 전달했으니 딱 이정도로 겹치는 연산이 발생했지만, 값이 클수록 했던 연산을 더 자주 하게 될 것이다.

문제에서 주어진 함수에 매개변수로 x를 넘긴다 가정하자
👉🏻 0~x까지의 매개변수를 받는 함수의 계산 과정에서 fibonacci(0), fibonacci(1) 연산이 몇 번 이루어지는지 저장하기 위한 fibonacci0, fibonacci1 배열을 선언했다.
👉🏻 초기값 대입
✔️ 매개변수가 0인 경우 fibonacci(0) 연산이 1번, fibonacci(1) 연산이 0번 이루어지므로 fibonacci0의 인덱스 0에 1을, fibonacci1의 인덱스 0에 0을 대입한다.
✔️ 매개변수가 1인 경우 fibonacci(0) 연산이 0번, fibonacci(1) 연산이 1번 이루어지므로 fibonacci0의 인덱스 1에 0을, fibonacci1의 인덱스 1에 1을 대입한다.
👉🏻 2~x까지 반복문을 돌며
fibonacci0[k] = fibonacci0[k-1] + fibonacci0[k-2];
fibonacci1[k] = fibonacci1[k-1] + fibonacci1[k-2];
연산을 수행해 몇 번의 연산이 이루어지는지 배열에 각각 저장한다.
👉🏻 최종적으로 각 배열의 인덱스 x에 저장되어 있는 값을 출력한다.

✨ 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            int[] fibonacci0 = new int[41];
            int[] fibonacci1 = new int[41];
            fibonacci0[0] = 1;
            fibonacci0[1] = 0;
            fibonacci1[0] = 0;
            fibonacci1[1] = 1;
            for(int k = 2; k <= N; k++){
                fibonacci0[k] = fibonacci0[k-1] + fibonacci0[k-2];
                fibonacci1[k] = fibonacci1[k-1] + fibonacci1[k-2];
            }
            System.out.println(fibonacci0[N] + " " + fibonacci1[N]);
        }
    }
}

👩🏻‍💻 후기

문제에 나온 함수를 똑같이 작성해 풀면 시간이 어떻게 나올까 궁금해서 한 번 해봤는데, 역시나 시간초과가 발생했다! 이번에는 저번에 dp 알고리즘으로 풀었던 것보다 수월하게 풀었다. 아무래도 익숙해서 그런가..? 대신 배열을 2개나 이용했는데 다음에 다시 풀 때는 지금보다 더 효율적으로.. 코드를 읽는데 어떤 방법으로 풀었는지 문제 풀이 흐름을 딱 이해할 수 있게 작성하려고 노력해야겠다!