#10870 피보나치 수 5

피보나치 수 5

10870

문제 풀이 전략

💡 fibo[1] = fibo[2] = 1; 과 같이 base case를 작성하면 0을 입력했을 때 런타임에러(ArrayIndexOfBound)가 발생함

코드

• Dynamic Programming으로 풀었을 경우 (재귀보다 메모리 사용량 적음)

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

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

        int n = Integer.parseInt(br.readLine()); // 몇 번째 피보나치 수
        int[] fibo = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if (i == 0) fibo[i] = 0;
            else if (i == 1 || i == 2) fibo[i] = 1;
            else fibo[i] = fibo[i - 1] + fibo[i - 2];
        }

        System.out.println(fibo[n]);

        br.close();
    }
}

• 재귀로 풀었을 경우

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

public class no_10870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); // 몇 번째 피보나치 수
        System.out.println(calcFibo(n));

        br.close();
    }

    public static int calcFibo(int n) {
        if (n == 0) return 0;
        else if (n == 1 || n == 2) return 1;
        else return calcFibo(n - 1) + calcFibo(n - 2);
    }
}