백준 1003 피보나치

dp 기본 유형인 피보나치..

를 풀기전에!!

우리 bottom up 과 top down에 대해서 짚고 넘어가자..

top-down

말그대로 위에서 아래로~~

큰거에서 작은걸로..그러면 어떻게 ?? 재귀를 타고 들어간다~

단 이렇게되면 제한적이다.하지만.. 점화식구할때는 엄청 편리하다 ㅎㅎ

bottom up

말그래도.. 아래서부터 차근차근 예를들면 1부터 10까지 차근차근 구하는방식

이렇게되면 메모리 제한도없고.. for문으로 구하는거기때문에 좋다..

하지만..그만큼 점화식을 구하기는 어렵다고보면된다..ㅎㅎ;;

다시문제로 ㄱㄱ

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

메인 로직

1. 0의사용 1의사용횟수이므로 class를 만들어준다
2. bottom up 방식으로 for문으로 구하기
3. 출력

소스코드는 다음과 같다.

import java.io.*;
public class 피보나치 {

	static class  fibo {
		int zeroc;
		int onec;
		public fibo(int zeroc, int onec) {
			this.zeroc = zeroc;
			this.onec = onec;
		}
		
		
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		fibo[] array = new fibo[41];
		array[0] = new fibo(1,0);
		array[1] = new fibo(0,1);
		for(int i=2;i<=40;i++) {
			int prevonec = array[i-2].onec + array[i-1].onec;
			int prevzeroc = array[i-2].zeroc + array[i-1].zeroc;
			array[i] = new fibo(prevzeroc,prevonec);
		}
		
		
		
		for(int i=0;i<tc;i++) {
			int cur = Integer.parseInt(br.readLine());
			fibo curfibo = array[cur];
			sb.append(curfibo.zeroc).append(" ").append(curfibo.onec).append("\n");
		}
			
		System.out.println(sb);
		
	}

}

굿 빠르게 실버를 돌파해보자~