[JAVA] 백준 10870 피보나치 수 5

10870번: 피보나치 수 5 (acmicpc.net)

10870번: 피보나치 수 5

 

- n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램 

 

- 피보나치 수는 0과 1로 시작. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1

- 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 됨 

 

Fn = Fn-1 + Fn-2 (n ≥ 2)

 

ex)

n=17

0,1.1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597

 

풀이 과정

 

 

28. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘 :: Simple in Complex with Simple (tistory.com)

28. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘

 

- 재귀적 방식, 동적 프로그래밍 방식, 반복적인 방식 존재 

- 동적과 반복은 기존 계산된 값을 저장할 테이블을 선언해야 함

 

재귀 

int fibo1(int n)
{
   if(n==0){
    	return 0;
    }
    else if(n==1){
    	return 1;
    }
    return fibo1(n-1)+fibo1(n-2);
}

 

동적

double fibo2(int n)
{
    if(memo[n]!= -1)
    {
    	return memo[n];
    }
    memo[n] = fibo2(n-1) + fibo2(n-2);
    return memo[n];
}

 

반복

double fibo3(int n)
{
    for(int i=2; i<n; i++) 
    {
    	memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n-1]+memo[n-2];
}

 

 

정답 

 

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

public class Main {
    public static int fibo(int n)
    {
        if(n==0) {
            return 0;
        }
        else if(n==1)
        {
            return 1;
        }
        
        return fibo(n-1)+fibo(n-2);
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        bw.write(fibo(n)+"");
        
        bw.flush();
        bw.close();
    }
}