[JAVA] 백준 1003번 : 피보나치 함수

 

- 초기 코드

  - 기존 피보나치 코드를 활용해서 풀었지만, 시간 초과가 떴다.

 

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

public class Main {
	
	static int N,num;	
	static int[] dp;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			dp = new int[2];
			num = Integer.parseInt(br.readLine());
			fibonacci(num);
			System.out.println(dp[0] + " " + dp[1]);
		}		
	}
	
	static void fibonacci (int n) {
		if (n==0) {
			dp[0] += 1;
		} else if (n==1) {
			dp[1] += 1;
		} else {
			fibonacci(n-1);
			fibonacci(n-2);
		}
	}
}

 

- 맞은 코드

  - 기존 피보나치 메소드를 사용하는 것이 아닌, 점화식을 통해서 풀었다.

 

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

public class Main {
	
	static int T,N;	
	static int[][] dp;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		dp = new int[41][2];
		
		dp[0][0] = 1;
		dp[1][1] = 1;
		
		for (int i = 2; i <41 ; i ++) {
			dp[i][0] = dp[i-1][0] + dp[i-2][0];
			dp[i][1] = dp[i-1][1] + dp[i-2][1];
		}
		
		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(br.readLine());
			System.out.println(dp[N][0] +" "+ dp[N][1]);
		}		
	}
}