[Java/백준/DP] 1003번: 피보나치 함수

문제

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

실패 코드(시간초과)

초과 뜰 것 같긴 했다 ㅎ...

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

class Main{
	static long[] zerone = new long[2];
	public static long fib(int n) {
		if(n==0) {
			zerone[0]++;
			return 0;
		}
		if(n==1) {
			zerone[1]++;
			return 1;
		}
		
		return fib(n-1)+fib(n-2);
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++) {
			zerone[0] = 0;
			zerone[1] = 0;
			
			int number = Integer.parseInt(br.readLine());
			fib(number);
			
			sb.append(zerone[0]+" "+zerone[1]+"\n");
		}
		
		bw.write(new String(sb));
		bw.flush();
	}
}

 

성공 코드

N일 때 0의 개수는 N-1의 0 개수 + N-2의 0 개수, 1의 개수는 N-1의 1 개수 + N-2의 1 개수이다.

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

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[][] zerone = new int[41][2];
		zerone[0][0] = 1;
		zerone[1][1] = 1;
		
		for(int i=2; i<41; i++) {
			for(int j=0; j<2; j++) {
				zerone[i][j] = zerone[i-1][j] + zerone[i-2][j];
			}
		}
		
		for(int i=0; i<n; i++) {
			int number = Integer.parseInt(br.readLine());			
			sb.append(zerone[number][0]+" "+zerone[number][1]+"\n");
		}
		
		bw.write(new String(sb));
		bw.flush();
	}
}