백준[JAVA] 1003. 피보나치함수

피보나치에서 다이나믹 프로그래밍으로 발전된 문제이다.

arr[n][2]의 저장소와 방문처리 boolean형 1차원 배열을 이용해 풀이했다.

arr[n][0]= n일 경우 0의 개수, arr[n][1]= n일 경우 1의 개수이다.

 

 

package algo;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class B_1003_피보나치함수 {
 
    static int[][] f = new int[41][2];
    static boolean[] visited = new boolean[41];
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        f[0][0] = f[1][1] = 1;
        f[0][1] = f[1][0] = 0;
        visited[0] = visited[1] = true;
        int T = Integer.parseInt(in.readLine());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(in.readLine());
            int[] result = fibo(n);
            sb.append(result[0] + " " + result[1] + "\n");
        }
        System.out.println(sb);
    }
 
    private static int[] fibo(int n) {
        int[] answer = new int[2];
        if (n == 0 || n == 1) {
            answer[0] = f[n][0];
            answer[1] = f[n][1];
            return answer;
        } else if (!visited[n]) { // 방문하지 않았을 때 - 배열에 값이 저장되지 않았을 경우
            visited[n] = true;
            int[] a = fibo(n - 1);
            int[] b = fibo(n - 2);
            f[n][0] = a[0] + b[0];
            f[n][1] = a[1] + b[1];
            answer[0] = f[n][0];
            answer[1] = f[n][1];
            return answer;
        } else { // 이미 해당 수의 계산이 끝나고 배열에 저장된 경우
            answer[0] = f[n][0];
            answer[1] = f[n][1];
            return answer;
        }
    }
}