2747번 : 피보나치 수

# 2747번 문제

유명한 피보나치 수에 대한 알고리즘

두 가지 방법으로 해결 가능

1. 재귀 호출

2. 반복문

 

처음엔 재귀호출을 이용하여 문제를 풀어보았다.

F_n = F_n-1 + F_n-2 (n>=2) 해당 식을 참고해서 재귀함수를 만든다.

import java.util.Scanner; public class Main { public static int fibonacci(int n){ if(n == 0) return 0; else if(n == 1) return 1; else return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); System.out.println(fibonacci(n)); } }

0과 1까지 호출한 후부터 차례대로 리턴하면서 값을 더하게된다.

하지만, 이렇게 풀면 시간 초과가 된다. 함수를 부르고 리턴하는 과정이 꽤나 오래걸림

 

그래서 두번째 방법인 반복문을 이용하여 도전.

마찬가지로 식을 참고하여 코드를 간단하게 작성.

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int n1 = 0; int n2 = 1; int n3 = 0; for(int i=0; i<n; i++){ n3 = n1+n2; n1 = n2; n2 = n3; } System.out.println(n1); } }

피보나치수의 첫번째는 0이 아니라 1이기 때문에 원하는 위치의 피보나치 수를 구하려면 첫번째 수를 출력해주어야 한다.