백준 17175. 피보나치는 지겨웡~

문제 바로가기

피보나치는 지겨웡~

문제 요약

피보나치 문제를 응용하여

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

이러한 피보나치 함수를 사용하여 fibonacci(n) 을 입력했을 때 fibonacci 함수가 몇회 호출되는지 확인하는 문제이다.

문제 풀이 포인트

일단 먼저 n이 50이하이기 때문에 숫자가 굉장히 크다. 그래서 출력값의 경우 1,000,000,007로 나눈 나머지를 출력해야 한다. 그리고 이런 DP 문제는 점화식을 세우는 것이 굉장히 중요한데 예시를 들어 살펴보자.

n이 4일 때 fibonacci(4)는 먼저 피보나치 함수를 1회 호출하고 fibonacci(3) 과 fibonacci(2) 함수를 각각 호출한다.

즉, fibonacci(n)은 fibonacci(n-1) + fibonacci(n-2) + 1 만큼 피보나치 함수를 호출하는 것이다. 이것을 점화식으로 세우면 f(n) = f(n-1) + f(n-2) + 1이다. 이제 기저 조건을 찾으면 되는데 f(0) = 1, f(1) = 1인 부분을 잘 캐치하자 정답 코드는 아래에 있다.

문제 코드[JAVA]

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
      dp[i] = dp[i-1] % 1000000007 + dp[i-2] % 1000000007 + 1;
      dp[i] = dp[i] % 1000000007; // 항상 나머지를 계산하는 습관을 들이자
    }
    System.out.println(dp[n]);
  }
}