21.09.12 기록

백준 알고리즘 1003 풀이

🎆나의 풀이(메모리 14MB, 시간 124ms로 통과)

-문제에서 주어진 재귀함수를 토대로 testCase를 7로 하여 2부터 8까지의 0과 1이 출력되는 횟수를 출력해보니 각 출력 결과도 피보나치 수열을 갖는 것을 확인했다.
-이를 응용하여 40번째까지 피보나치 수를 fibonacci 배열로 저장한 후, 각 테스트 케이스를 배열의 인덱스로 활용하여 값을 구하였다.

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

public class B1003 {
    public static int[] fibonacci = new int[40+1];

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

        getFibonacci();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < testCase; i++) {
            int num = Integer.parseInt(br.readLine());

            if(num == 0) {
                sb.append("1 0").append("\n");
            } else if(num == 1) {
                sb.append("0 1").append("\n");
            } else {
                sb.append(fibonacci[num-1]).append(" ").append(fibonacci[num]).append("\n");
            }
        }
        System.out.println(sb);
    }

    public static void getFibonacci() {
        fibonacci[0] = 0;
        fibonacci[1] = 1;

        for(int i = 2; i < fibonacci.length; i++) {
            fibonacci[i] = (fibonacci[i-1]+fibonacci[i-2]);
        }
    }
}

🎆해설(메모리 14MB, 시간 124ms로 통과)

• 동적 계획법, Dynamic Programming
  

  재귀호출을 할 때 이미 한 번 탐색(연산)했던 값이라면, 이미 이전에 계산된 값을 재사용하여 반복적인 연산과정을 줄이는 방법을 기초로 한다.
  

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

public class B1003 {
    //null을 사용하기 위해 Integer형 배열을 사용했다.
    public static Integer[][] dp = new Integer[41][2];

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

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

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

    public static Integer[] fibonacci(int N) {
        //N에 대한 0, 1의 호출 횟수가 없을 때(탐색하지 않은 값인 경우)
        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];
    }
}