백준 10870번 문제풀이 - 피보나치 함수

백준 10870번 문제

 

 

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

10870번: 피보나치 수 5

 

이번 문제는 피보나치 함수를 재귀를 사용하여 풀어보는 문제이다.

피보나치 수는 𝐹𝑛 = 𝐹𝑛-1 + 𝐹𝑛-2 (n ≥ 2)로 정의된다.

0번 째 수는 0, 1번 째 수는 1로 정의됐기 때문에 메서드를 만들 때 f(0)은 0, f(1)은 1로 리턴하도록 하고

재귀하며 반복적으로 덧셈을 수행하도록 했다.

 

 

 

 

 

코딩

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

public class Fibonacci {
    // 피보나치 함수
    static int fibo(int f) {
        if (f > 1) {
            return fibo(f-1) + fibo(f-2); // 피보나치 알고리즘
        } else if (f == 1) { // 1일 때 1
            return 1;
        } else { // 0일 때 0
            return 0;
        }
    }

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

        System.out.println(fibo(n));
    }
}

 

 

 

 

 

 

결과

 

 

 

 

 

느낀 점

 

간단한 문제라서 푸는데 얼마 걸리지 않고 복잡하지 않았지만 하노이의 탑이나 8퀸 문제와 같은 고난이도로 올라가면 복잡해져서 재귀문에 대해 좀 더 익숙해지고 깊이있게 이해할 필요가 있을 것 같다.