[백준] 10870번: 피보나치 수 5 (Java)

1. 문제설명

n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

• 재귀 방법을 사용한다.
• 피보나치 메서드
  • 합을 구한 두 개의 값을 매개변수로 받는다.
  • 두 개의 합을 구하고 저장한 뒤, 구한 합과 두 번째 매개 변수로 재귀 호출한다.
  • n번째 피보나치 수를 구한 경우 종료한다.
• 단, n이 0이면 0을 출력, 1이면 1을 출력한다.
  그 외의 숫자는 피보나치 메서드를 호출한다.

 

3. 올바른 접근 방식 및 해결 방식

• 재귀 방법을 사용해 피보나치 수를 구한다.
• n이 0과 1일 경우는 fibonacci 메서드를 호출하면 에러가 발생하기 때문에 따로 체크해주어야 한다.

 

4. 최종 코드

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

public class BJ_10870 {
    static int n; 
    static int count = 1; // 순서 1부터 시작
    static int result = 0; // 피보나치 수 저장

    static void fibonacci(int a, int b) {
        if(count == n) { // 현재 순서가 n번째 이면
            System.out.println(result); // 현재 피보나치 수 출력
            return; // 종료
        }
        result = a + b; // 두 매개변수 값을 더하고 저장
        count++; // 현재 순서 갱신
        fibonacci(b, result); // 메서드 재귀 호출
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        if(n==0) System.out.println(0); // n이 0이면 0을 출력
        else if(n==1) System.out.println(1); // n이 1이면 1을 출력
        else fibonacci(0, 1); // n이 2이상이면 fibonacci 메서드 호출
    }
}

 

5. 시간복잡도

$O(n)$