Q7 - 4 피보나치 수열

피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.

입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

 

* 입력설명

첫 줄에 총 항수 N(3<=N<=45)이 입력된다.

 

* 출력설명

첫 줄에 피보나치 수열을 출력합니다.

 

* 입력예제 1 

10

* 출력예제 1

1 1 2 3 5 8 13 21 34 55

 

 

 

import java.util.Scanner;

public class Main {
	
	public int DFS1(int n) {
		if(n==1) {
			return 1;
		}else if(n==2){
			return 1;
		}else {
			return DFS1(n-2)+DFS1(n-1);
		}
	}
	
	static int[] fibo;
	public int DFS2(int n) {
		if(n==1) {
			return fibo[n]=1;
		}else if(n==2){
			return fibo[n]=1;
		}else {
			return fibo[n]=DFS2(n-2)+DFS2(n-1);
		}
	}
	
	public int DFS3(int n) {
		if(fibo[n]>0) return fibo[n];
		if(n==1) {
			return fibo[n]=1;
		}else if(n==2){
			return fibo[n]=1;
		}else {
			return fibo[n]=DFS2(n-2)+DFS2(n-1);
		}
		
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner in = new Scanner(System.in);
		int in1 = in.nextInt();
		in.close();
		
//		방법 1
//		for(int i = 1; i <= in1; i++) {
//			System.out.print(T.DFS1(i) + " ");	
//		}
		
//		방법 2
//		fibo = new int[in1+1];
//		T.DFS2(in1);
//		for(int i = 1; i <= in1; i++) {
//			System.out.print(fibo[i] + " ");
//		}

//		방법 3
		fibo = new int[in1+1];
		T.DFS3(in1);
		for(int i = 1; i <= in1; i++) {
			System.out.print(fibo[i] + " ");
		}
		
		
	}
}