[백준 1003] 피보나치 함수 (JAVA)

백준 1003번 문제 - 피보나치 함수

1003번: 피보나치 함수

---

문제 분석

 

 

• N번째 피보나치 수를 구하는 다음 C++ 함수를 실행했을 때, N이 입력됬을 때 0과 1이 프린트되는 횟수를 출력해라.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

---

 

해결 키 포인트

 

• DP로 구현
  • DP가 아니면 시간초과 발생
• 피보나치 수를 구하는 함수의 규칙을 보면,
  결국에 fibonacci(n-1)의 0과 1이 프린팅 되는 횟수 +  fibonacci(n-2)의 0과 1이 프린팅 되는 횟수이다. 
• fibonacci(0)하고 fibonacci(1)은 결과 값이 정해져있으므로 fibonacci(2)부터 값 구하기
  • dp[n]의 0프린팅 횟수 = dp[n-1] 0프린팅 횟수 + dp[n-2] 0프린팅 횟수
  • dp[n]의 1프린팅 횟수 = dp[n-1] 1프린팅 횟수 + dp[n-2] 1프린팅 횟수

---

코드

 

import java.io.*;

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

        dp = new int[41][2];
        dp[0] = new int[]{1, 0};
        dp[1] = new int[]{0, 1};
        for (int i = 2; i < 41; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }

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

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());

            bw.write(dp[n][0] + " " + dp[n][1] + "\n");
        }
        bw.flush();
        bw.close();
    }
}