본문 바로가기

Java/백준

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

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

 

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

 

- 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. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘

1. 개요 피보나치 수열의 알고리즘은 정말 쉬움. 크게 3가지 방식 존재. (1) 재귀(recursion), (2) 동적 프로그래밍(Dynamic Programming), (3) 반복(For문) 피보나치 수열의 BigO()는 방식에 따라 다름. (1) 재귀: B

makefortune2.tistory.com

 

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

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

 

재귀 

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();
    }
}