[BOJ] 17175 피보나치는 지겨웡~ (Week 7, No.11)

문제

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.

int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  }  
  return fibonacci(n-2) + fibonacci(n-1);
}

위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.

입력

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

출력

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

3

예제 출력 2

5

---

풀이

직접 fibonacci()를 돌면서 count를 세도 되지만, 그렇게 하면 시간 초과가 된다.
그래서 각각의 n일 때 fibonacci()를 수행하는 횟수를 배열에 적어두어, 작은 수부터 큰 수까지 두 횟수를 더해가면서 구한다.

횟수가 많이 나올 수 있기 때문에, 모든 횟수를 구할 때 % 1000000007을 한 뒤 배열에 넣었다.

n이 2보다 작을 경우에는 fibonacci()가 한번만 수행되고,
n=2일 경우에는 fibonacci()도 1번 실행되고, n=0인 경우와 n=1인 경우의 횟수를 더하면 되기 때문에 두 경우의 횟수를 더하고 1을 더해서 횟수를 구한다.
n이 그 이상일 때도 위와 같이 구한다.

시간복잡도: O(N) - bottom up 방식으로 n까지 실행된다.
공간복잡도: O(N) - 각 경우의 값을 저장하는 배열을 사용한다. (그런데 현재 값을 구하기 위해서는 이전의 2개의 값만 필요하기 때문에 O(1)이 될 수 있다.)

---

코드

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 n = Integer.parseInt(br.readLine());

        // base case
        if (n < 2) {
            System.out.println(1);
            return;
        }
        
        int[] fiboCount = new int[n + 1];

        fiboCount[0] = 1 % 1000000007;
        fiboCount[1] = 1 % 1000000007;

        for (int i = 2; i <= n; i++) {
            fiboCount[i] = (fiboCount[i - 2] + fiboCount[i - 1] + 1) % 1000000007;
        }
        System.out.println(fiboCount[n]);
    }
}