[JAVA] 백준 알고리즘 10870번 피보나치 수열

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

피보나치 수열은 문제에도 나와있듯 2번째 수 부터 그 앞에 있는 두 수의 합이 되는 형태로 수열 값은

0, 1, 1, 2, 3, 5, 8, 13, 21 … 로 나타난다.

 

해결 방법을 모를 때는 변수 두개를 선언하여 이전 값을 저장하는 식으로 알고리즘을 짜려했지만 잘 되지 않았다.

여러 방법을 생각해보다 이곳저곳 찾아보다 발견한 방법은 재귀함수를 사용하는 것이다.

재귀함수에 대한 내용은 다른 포스트에서 다루도록 하겠다.

 

다시 본 문제로 돌아와서 어떻게 해결하였는지를 살펴보자.

 

코드를 보게되면

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

		int max = sc.nextInt();

		if (max >= 0 && max <= 20)
			System.out.println(fibo(max));

	}

	static int fibo(int max) {

		if (max <= 1) {

			return max;

		} else {

			return fibo(max - 2) + fibo(max - 1);

		}

	}

}

 

위와 같은 식으로 스캐너로 확인하고 싶은 피보나치 수열의 번호를 입력받아 함수로 넘겨주게 된다.

여기서 함수를 보게되면, fibo()라는 함수내부에서 또 다시 fibo()라는 함수를 호출하는 재귀함수 형식으로 구성되어있다.

예를 들어 fibo()의 매개변수로 10을 넘기면

fibo(10)가 fibo(9)와 fibo(8)을 호출하게 되고 fibo(9)와 fibo(8)은 각각 fibo(7),fibo(8) / fibo(6),fibo(5)를 호출하게 된다.

이런식으로 fibo(1)과 fibo(0)이 호출될때까지 반복된다.

fibo()함수는 매개변수의 값이 1이하면 그대로 반환해주기 때문에 fibo(0)일때는 제외하고 fibo(1)가 호출된 횟수가 곧 수열의 값이 된다.