백준 알고리즘 1003

동적 계획법 : 처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것

첫번째 제출

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

public class Main {
    static int fibo0;
    static int fibo1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        int[] tests = new int[test];

        for(int i=0; i<test; i++){
            tests[i] = Integer.parseInt(br.readLine());
        }

        for(int result : tests){
            fibo0 = 0;
            fibo1 = 0;
            fibonacci(result);
            System.out.println(fibo0 + " " + fibo1);
        }
    }

    static int fibonacci(int n) {

        if( n == 0 ){
            fibo0++;
            return 0;
        }
        if( n == 1 ){
            fibo1++;
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

시간 초과떴다. 그렇다면 0과 1을 출력한 횟수를 저장해서 이전에 계산한 값을 다시 계산하지 않도록 해보자

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

public class Main {

    static Integer[][] dp = new Integer[41][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        dp[0][0] = 1; //T=0일때 0호출 횟수
        dp[0][1] = 0; //T=0일때 1호출 횟수
        dp[1][0] = 0; //T=1일때 0호출 횟수
        dp[1][1] = 1; //T=1일때 0호출 횟수

        while(T-- > 0){
            int N = Integer.parseInt(br.readLine());
            fibonacci(N);
            sb.append(dp[N][0] + " " + dp[N][1]).append("\n");
        }
        System.out.println(sb);
    }

    static Integer[] fibonacci(int T) {
        if( dp[T][0] == null || dp[T][1] == null) {
            // 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.
            dp[T][0] = fibonacci(T - 1)[0] + fibonacci(T - 2)[0];
            dp[T][1] = fibonacci(T - 1)[1] + fibonacci(T - 2)[1];
        }
        return dp[T];
    }
}

---

StringBuilder을 이용해 담아두고 나중에 한번 출력하면 된다.
계산하는 반복문과 출력하는 반복문을 따로 두지 말고..
자바 이중배열을 생각못했다