백준 10870 - 피보나치 수

문제파악

피보나치 수를 구하는 문제

피보나치 수란 ? 첫째, 둘째 항이 1이고 그 뒤의 모든 항은 바로 앞 두 항의 합으로 이루어진 수열
알고리즘에서 재귀를 다룬 문제로 자주 등장!

풀이

1. 몇 번째 피보나치 수를 구할건지의 n을 입력받는다. (스캐너)
2. 피보나치 함수를 구현한다.
   a. 인자로 n을 받는다.
   b. base case - 만약 첫 번째나 두 번째면 1 리턴
   c. 아니면 재귀 호출 - n-1과 n-2의 합 -> 스택오버플로우 발생..
   => DP(Bottom Up 방식) - 배열을 활용해 이전의 수열 값을 저장해 스택오버플로우를 발생시키지 않음
   a. 배열의 첫 번째 값 0, 두세 번째 인덱스 값은 1로 설정 - 이것도 n이 0이나 1일 가능성 때문에 에러 처리를 해주어야 함(if문)
   b. n이 2 이상인 경우 반복문을 돌려 n 번째 수열 찾기
3. 피보나치 함수를 출력한다.

코드

import java.util.Scanner;

public class 피보나치_수_5 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //몇 번째 피보나치 수인지
        int n = sc.nextInt();

        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n) {
        //배열에 수열 저장
        int[] fibo = new int[n + 1];
        //만약 n이 0인 경우 0 리턴
        if (n == 0) {
            return 0;
            //n이 1일 경우 1 리턴
        } else if (n == 1) {
            return 1;
        }
        //n이 2 이상일 경우 반복
        for (int i=2; i<=n; i++) {
            fibo[0] = 0;
            fibo[1] = 1;
            fibo[i] = fibo[i - 2] + fibo[i - 1];
        }
        return fibo[n];
    }
}