Java) 백준 1003번 피보나치 함수 (DP)

 

피보나치 함수를 이용하여 0과 1의 사용빈도를 출력하는 문제입니다.

이 문제는 다이나믹 프로그래밍을 사용해야 합니다!

 

1. 재귀
2. Top-Down
3. Bottom-Up

---

1. 재귀

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

public class Main {
	static int count_0 = 0;
	static int count_1 = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		for(int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			Fibonacci(m);
			bw.write(count_0 + " " + count_1 + "\n");
			count_0 = 0;
			count_1 = 0;
		}
		br.close();
		bw.flush();
		bw.close();
	}

	private static int Fibonacci(int n) {
	    if (n == 0) {
	    	count_0++;
	        return 0;
	    } else if (n == 1) {
	    	count_1++;
	    	return 1;
	    } else {
	    	return Fibonacci(n - 1) + Fibonacci(n - 2);
	    }
	}
}

재귀로 풀어봤으나 시간 초과가 납니다.

그러면 다른 두 방법으로 풀어보겠습니다!

 

2. Top-Down

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

public class Main {
    static Integer[][] dp = new Integer[41][2];

    static Integer[] fibonacci(int n) {
        if(dp[n][0] == null || dp[n][1] == null) {
            dp[n][0] = fibonacci(n - 1)[0] + fibonacci(n - 2)[0];
            dp[n][1] = fibonacci(n - 1)[1] + fibonacci(n - 2)[1];
        }
        return dp[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            fibonacci(N);
            bw.write(dp[N][0] + " " + dp[N][1] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

3. Bottom Up

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

public 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));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            int m = Integer.parseInt(br.readLine());
            ArrayList<Integer> zeroCount = new ArrayList<>();
            ArrayList<Integer> oneCount = new ArrayList<>();
            zeroCount.add(1); // 0 at index 0
            zeroCount.add(0); // 0 at index 1
            oneCount.add(0); // 1 at index 0
            oneCount.add(1); // 1 at index 1
            for(int j = 2; j <= m; j++) {
                zeroCount.add(zeroCount.get(j - 1) + zeroCount.get(j - 2));
                oneCount.add(oneCount.get(j - 1) + oneCount.get(j - 2));
            }
            bw.write(zeroCount.get(m) + " " + oneCount.get(m) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}