[BOJ] 1003. 피보나치 함수

문제

BOJ 1003. 피보나치 함수

풀이

bottom-up과 top-down 두 가지 방식으로 풀었다.
시간 제한이 0.25초였기 때문에 BufferedReader와 StringBuilder를 사용했다.
처음에 bottom-up으로 풀 때는 조금 비효율적인 방법으로 풀은 것 같았다.
재귀를 이용한 top-down으로 풀면서 DP배열 활용에 대해 고민을 좀 더 했던 것 같다.

JAVA코드

• bottom-up

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

public class 백준1003_피보나치함수 {

	/*
	 * int[][] dp; // 0 : 0의 개수, 1 : 1의 개수
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		int[][] DP = new int[41][2];
		DP[0][0] = 1;
		DP[0][1] = 0;
		DP[1][1] = 1; // 0과 1의 개수 카운트
		DP[1][0] = 0;
		
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			

			for (int j = 2; j <= N; j++) {
				DP[j][0] = DP[j-1][0]+DP[j-2][0];
				DP[j][1] = DP[j-1][1]+DP[j-2][1];
			}
			
			sb.append(DP[N][0]+" "+DP[N][1]+"\n");
		}
		
		System.out.print(sb);

	}

}

• top-down

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

public class 백준1003_피보나치함수2 {

	/*
	 * int[][] dp; // 0 : 0의 개수, 1 : 1의 개수
	 */
	static int[][] DP = new int[41][2];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		
		DP[0][0] = 1;
		DP[0][1] = 0;
		DP[1][1] = 1; // 0과 1의 개수 카운트
		DP[1][0] = 0;
		
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			
			fibo(N);
			sb.append(DP[N][0]+" "+DP[N][1]+"\n");
		}
		
		System.out.print(sb);

	}
	
	public static int[] fibo(int N) {
		if(N>=2&& (DP[N][0]==0 || DP[N][1]==0)) {
				DP[N][0] = fibo(N-1)[0]+fibo(N-2)[0];
				DP[N][1] = fibo(N-1)[1]+fibo(N-2)[1];
		}
		
		return DP[N];
	}

}