[실버3, DP] 백준 1003 - 피보나치 함수 (자바)

Think

1. 점화식이 주어졌기때문에 그나마 간단하게 풀었음.

2. 0의 개수와 1의 개수를 세야하니 처음에는 객체로 풀었음

3. https://st-lab.tistory.com/124 를 보니, 2차원배열로도 풀 수 있다는걸 확인함

 

 

객체코드1 (2차원배열 사용)

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

public class test {
    static int n, t;
    static Integer dp[][];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
    }

    private static void progress() {
        fibonacci(n);

        System.out.println(dp[n][0] + " " + dp[n][1]);
    }

    private static Integer[] fibonacci(int number) {

        if(dp[number][0] == null || dp[number][1] == null){
            dp[number-1] = fibonacci(number - 1);
            dp[number-2] = fibonacci(number - 2);

            dp[number][0] = dp[number-1][0] + dp[number-2][0];
            dp[number][1] = dp[number-1][1] + dp[number-2][1];

//            dp[number][0] = fibonacci(number - 1)[0] + fibonacci(number - 2)[0];
//            dp[number][1] = fibonacci(number - 1)[1] + fibonacci(number - 2)[1];
        }

        return dp[number];

    }

    private static void init() throws IOException {
        t = Integer.parseInt(br.readLine());
        dp = new Integer[41][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());

            progress();
        }
    }

    public static class Count{
        int zero;
        int one;

        public Count(int zero, int one){
            this.zero = zero;
            this.one = one;
        }
    }

}

 

 

 

 

제출코드2 (객체 사용)

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

public class test {
    static int n, t;
    static Count dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
    }

    private static void progress() {
        Count fibonacci = fibonacci(n);

        System.out.println(fibonacci.zero + " " + fibonacci.one);
    }

    private static Count fibonacci(int number) {
//        if(number == 0){
//            return dp[0];
//        }else if(number == 1){
//            return dp[1];
//        }else if(number == 2){
//            return dp[2];
//        }

        if(dp[number] == null){
            Count fibo1 = fibonacci(number - 1);
            Count fibo2 = fibonacci(number - 2);

            dp[number] = new Count(fibo1.zero + fibo2.zero, fibo1.one+ fibo2.one);
        }

        return dp[number];

    }

    private static void init() throws IOException {
        t = Integer.parseInt(br.readLine());
        dp = new Count[41];
        dp[0] = new Count(1,0);
        dp[1] = new Count(0,1);
        dp[2] = new Count(1,1);

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());

            progress();
        }
    }

    public static class Count{
        int zero;
        int one;

        public Count(int zero, int one){
            this.zero = zero;
            this.one = one;
        }
    }

}