[코드트리] 함수 실행 횟수 - 자바(Java)

문제

https://www.codetree.ai/problems/number-of-function-executions?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

다음과 같은 코드에서, codetree(n)을 실행하였을 때, codetree 함수가 호출되는 횟수를 구하는 프로그램을 작성해보세요.

 

입력 예시

2

 

출력 예시

3

 

 

코드

첫 번째 줄에 n이 주어집니다.

• 1 ≤ n ≤ 50

 

codetree 함수가 호출된 횟수를 1,000,000,007로 나눈 나머지를 출력합니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        dp[0] = 1; // 0의 호출 횟수
        dp[1] = 1; // 1의 호출 횟수
        for (int i = 2; i <= n; i++) {
            // i-1의 호출 횟수 + i-2의 호출횟수 + 1
            dp[i] = dp[i - 1] + dp[i - 2] + 1;
        }

        bw.write(String.valueOf(dp[n] % 1000000007));
        bw.flush();
        bw.close();
    }
}