[백준] 피보나치 함수 1003번

코드 힌트

1. 피보나치 수 파악하기:
   • 피보나치 수열의 규칙은 n = (n-1) + (n-2)입니다.
   • 예를 들어, n이 4라면, f(4) = f(3) + f(2)입니다.
2. 0과 1의 호출 횟수 구하기:
   • 피보나치 수를 계산하는 과정에서 f(0)과 f(1)이 호출되는 횟수를 찾는 문제입니다.
   • n이 0과 1일 때를 제외하고, f(0)의 호출 횟수는 piboArr[n-1], f(1)의 호출 횟수는 piboArr[n]입니다.
   • 문제에서 주어지는 n의 범위가 0에서 40이므로, 미리 0부터 40까지의 피보나치 수를 계산해두면 빠르게 답을 찾을 수 있습니다.

규칙을 파악해서 코드로 작성해보세요

n	f(0)	f(1)
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

 

---

정답은 더보기 클릭

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 입력받은 테스트 케이스의 수
        int len = Integer.parseInt(in.nextLine());
        
        // 피보나치 배열 생성 (0~40의 피보나치 수 저장)
        int[] piboArr = new int[41];
        piboArr[0] = 0;
        piboArr[1] = 1;
        for (int i = 2; i <= 40; i++) {
            piboArr[i] = piboArr[i-1] + piboArr[i-2];
        }
        
        // 테스트 케이스마다 결과 출력
        for (int i = 0; i < len; i++) {
            int n = Integer.parseInt(in.nextLine());
            
            if (n == 0) {
                System.out.println(piboArr[1] + " " + piboArr[0]);
            } else if (n == 1) {
                System.out.println(piboArr[0] + " " + piboArr[1]);
            } else {
                System.out.println(piboArr[n-1] + " " + piboArr[n]);
            }
        }
    }
}