[JAVA] 백준 2748 : 피보나치 수 2

백준 2748 : 피보나치 수 2

 

문제 링크

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

 

문제 내용

(요약) 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn=Fn-1+Fn-2(n>=2)가 된다.

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

Idea

피보나치 수열이란 앞의 두 수를 더한 값이 자신의 값이 되는 수열이다.

첫번째 항은 0, 두번째 항은 1로 시작하여

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

이와 같이 증가한다.

 

코드는 배열을 사용한다고 했을 때, 문제에 나온 점화식을 사용하면 된다.

F[n] = F[n-1] + F[n-2] (단, n >=2 일 때)

 

번외로 재귀함수를 사용하여 푸는 방법도 있다.

 

 

Code

import java.util.Scanner;
 
public class Main {
    int n;
    
    public Main(int n) {
        this.n = n;
    }
    
    void fibo() {
        long arr[]=new long[91];
 
        //0번째와 1번째 수는 지정해준다.
        arr[0]=0;
        arr[1]=1;
        
        //피보나치 수열을 계산하는 반복문
        for(int i=2;i<=n;i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        
        //n번째 숫자를 
        System.out.println(arr[n]);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        new Main(n).fibo();
    }
}