[ 백준 / BOJ 17175 ] 피보나치는 지겨웡~ ( 자바 / JAVA )

https://www.acmicpc.net/problem/17175

17175번: 피보나치는 지겨웡~

 

문제

---

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

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 로 나눈 나머지를 출력한다.

코드

---

import java.util.Scanner;

public class Main_BOJ_17175_피보나치는지겨워 {
    static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[51];

        dp[0] = 1;
        dp[1] = 1;

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