[백준][Java] 17175 - 피보나치는 지겨웡~

 

목차

 

 

문제 정보

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

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

난이도 : S3

유형 : DP

시간 : O(N)

---

문제 풀이

fibonacci 함수가 호출된 횟수를 구해야 한다.

 

fibonacci의 정의를 생각해 보자

fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1]  ( i < 2 -> return i)

 

피보나치함수 인자가 0 혹은 1 일 때 값을 리턴하고 종료하며

예외의 상황일 때 위의 식처럼 재귀문의 형태로 반복된다.

 

 

일단 함수가 종료되는 상황에 집중하자

함수가 호출된 횟수를 알려면 함수가 종료되는 시점을 알아야 한다. (함수가 종료되면 그 함수는 더 이상 재귀를 반복하지 않기 때문에)

피보나치는 함수는 인자가 0 혹은 1 일 때 종료된다.

 

즉 피보나치함수가 재귀를 반복하여 0 혹은 1을 몇 번 리턴하는지만 알면 된다.

 

그러나 우리는 재귀대신 메모제이션 기법으로 더 빠르게 답을 알아낼 수 있다.

 

현재 구하려는 피보나치함수의 호출값은 이전 피보나치함수의 값을 재활용하여 구할 수 있다.(위의 피보나치 정의식 참고)

dp[i] = (dp[i - 2] + dp[i - 1] + 1) % 1_000_000_007. //점화식

 

피보나치 함수는 0과 1일 때 종료를 하니

dp[0] = 1; dp[1] = 1; 로 초기화 해준다.( dp 배열은 함수 호출 횟수를 저장한다 )

 

예를 들어 "피보나치함수_3"을 구하고 싶으면

이전에 미리 구해놓은 "피보나치함수_1"의 값 + "피보나치함수_2"의 값에 "피보나치함수_3 본인이 본인을 호출 (1)"을 더하면 된다.

 

---

코드

// author : DDing77

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

public class Main {

    final int MOD = 1_000_000_007;
    int N;
    int[] dp;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        
        if (N < 2) {
            System.out.println(1);
            return;
        }

        dp = new int[N + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1] + 1) % MOD;
        }

        System.out.println(dp[N]);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}