2022.03.25 90일차

백준 17175번 (피보나치는 지겨웡~)

문제

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

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

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

나의 풀이

1. 작은 부분부터 생각하기
   0 => 1
   1 => 1
   2 => 3
   3 => 5
   4 => 9
   5 => 15
   6 => 25
   ...
2. dp[n - 1] + dp[n - 2] + 1

import java.io.*;
import java.util.*;

public class Main {
    static long[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        dp = new long[51];

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {

            dp[i] = dp[i - 1] + dp[i - 2] + 1;
        }

        System.out.println(dp[n] % 1000000007);
    }
}

생각하기

• DP 문제 풀이 연습