BOJ 2748 - 피보나치 수 2

문제

N이 주어질 때 N번째 피보나치 수를 구하라. 피보나치 수는 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)로 정의된다.

입력

N이 주어진다 (0 이상 90 이하).

출력

N번째 피보나치 수를 출력한다.

예제

입력	출력
`10`	`55`

풀이

메모이제이션을 사용한 재귀로 피보나치 수를 구한다.

배열 arr[]을 Long 타입으로 선언하고 arr[0]=0, arr[1]=1로 초기화한다
재귀 호출 시 arr[n]이 null이면 recur(n-1) + recur(n-2)를 계산하여 저장한다
이미 계산된 값은 배열에서 바로 반환한다

핵심 아이디어: N이 최대 90이므로 long 타입이 필요하며, 메모이제이션으로 중복 계산을 제거하여 O(N)에 해결한다.

코드

package day449;
 
import java.io.*;
 
public class Day422BOJ2748피보나치수 {
  static Long[] arr;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    int N = Integer.parseInt(br.readLine());
 
    arr = new Long[N + 1];
 
    arr[0] = 0L;
    arr[1] = 1L;
    System.out.println(recur(N));
  }
 
  public static long recur(int n) {
    if (arr[n] == null) {
      arr[n] = recur(n - 1) + recur(n - 2);
    }
    return arr[n];
  }
}

복잡도

시간: O(N)
공간: O(N)

문제