[백준] S3 17175번 피보나치는 지겨웡~ (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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

---

[풀이]

1. 접근에서 찾은 dp 식을 통해 문제를 해결하였다.

[접근]

1. 피보나치 실행횟수를 생각해 보니 dp 식을 아래와 같이 세울 수 있었다

0 : fibonacci(0) 호출 >> 1번 호출
1 : fibonacci(1) 호출 >> 1번 호출
2 : fibonacci(2) 호출 >> fibonacci(1), fibonacci(0) 호출 >> 3번 호출
3 : fibonacci(3) 호출 >> fibonacci(2), fibonacci(1) 호출 >> 1 + fibonacci(2) + fibonacci(1) = 1 + 3 + 1 >> 5번 호출
4 : fibonacci(4) 호출 >> fibonacci(3), fibonacci(2) 호출 >> 1 + fibonacci(3) + fibonacci(2) = 1 + 5 + 3 >> 9번 호출

>>> 자기자신 호출 1번 + n-1 호출 횟수 + n-2 호출 횟수

dp[n] = 1 + dp[n-1] + dp[n-2]

[코드]

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 선언 및 초기화
		long[] dp = new long[51];
		dp[0] = 1;
		dp[1] = 1;
		
		// n 입력받기
		int n = Integer.parseInt(br.readLine());
        
		// 피보나치 실행 횟수 = 1 + dp[i-1] + dp[i-2]
        for (int i = 2; i <= n; i++) {
            dp[i] = (1 + dp[i-1] + dp[i-2]) % 1000000007;
        }
        
        System.out.print(dp[n]);
	}
}