백준 1003 : 피보나치 함수 _자바 Java

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

1003번: 피보나치 함수

 

---

1. 실패코드(시간초과로 실패)

import java.io.*;
import java.util.*;

public class Main {
	
	static int cZero=0,cOne=0;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tCase = Integer.parseInt(br.readLine());
		
		for(int i=0;i<tCase;i++) {
			int t=Integer.parseInt(br.readLine());
			fibonacci(t);
			System.out.println(cZero+" "+cOne);
			cZero=0;
			cOne=0;
		}
		
		
			
	}
	static int fibonacci(int n) {
	    if (n == 0) {
	    	cZero++;
	        return 0;
	    } else if (n == 1) {
	    	cOne++;
	        return 1;
	    } else {
	        return fibonacci(n-1) + fibonacci(n-2);
	    }
	}
}

이 문제의 분류가 다이나믹 프로그래밍으로 되어있는 것을 확인하고 규칙이 존재하는지 확인해봤다. 
그래서 이걸 바탕으로 결과를 여러개 출력해봄.

 

 

2부터 앞에 있는 두 수의 각 0 과 1 의 호출 횟수를 더하면 해당 수의 0 과 1 호출 횟수가 되는 것을 발견!

그래서 

import java.io.*;
import java.util.*;

public class Main {
	
	static int[][] f =new int[41][2];
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tCase = Integer.parseInt(br.readLine());
			
		f[0][0]=1;
		f[0][1]=0;		
		f[1][0]=0;
		f[1][1]=1;

		for(int i=2;i<41;i++) {
			f[i][0]=f[i-1][0]+f[i-2][0];
			f[i][1]=f[i-1][1]+f[i-2][1];
		}

		for(int i=0;i<tCase;i++) {
			int t=Integer.parseInt(br.readLine());
			System.out.println(f[t][0]+" "+f[t][1]);
		}
		
	}
	
}

성공함.