[백준 1003] 피보나치 함수

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

역시나 피보나치 문제입니다. 

일단 fibo(n)에 대한 fibo(0)과 fibo(1)의 호출 횟수를 구하는 문제입니다.

두 값을 더하면 저희가 일반적으로 생각하는 피보나치 수열이 나오게 되죵..

일단 실행시간이 0.25초여서 재귀는 사용하지 않았습니다. 

사실 첫방에 통과 못할줄 알고 그냥 코드 넣어봤는데 됫네요.

 

public class Q1003 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int[] temp = new int[num];
		int max = 0;
		for(int i=0; i<temp.length; i++) {
			temp[i] = Integer.parseInt(br.readLine());
			if(max<temp[i]) {
				max = temp[i];
			}
		}
		
		ArrayList<Cnt> al = new ArrayList<Cnt>();
		for(int i=0; i<=max; i++) {
			if(i==0) {
				al.add(new Cnt(1, 0));
			}else if(i==1) {
				al.add(new Cnt(0, 1));
			}else {
				int zc = al.get(i-1).getZero() + al.get(i-2).getZero();
				int oc = al.get(i-1).getOne() + al.get(i-2).getOne();
				al.add(new Cnt(zc, oc));
			}
		}
		for(int i=0; i<temp.length; i++) {
			System.out.println(al.get(temp[i]).getZero()+" "+al.get(temp[i]).getOne());
		}
	}
}
class Cnt{
	private int zero;
	private int one;
	
	public Cnt(int zero, int one) {
		this.zero = zero;
		this.one = one;
	}
	public int getZero() {
		return this.zero;
	}
	public int getOne() {
		return this.one;
	}
}

 

0과 1호출 수를 저장하는 객체를 만들고 이것을 ArrayList에 담는 식으로 풀었습니다

그리고 0과 1부분 처리만 해주고 

배열로 구하는 피보나치 문제처럼 풀었습니다