[Java] 백준 1003번 (피보나치 함수) [실버3]

https://www.acmicpc.net/problem/1003

난 DP가 싫다. 하지만 이 문제는 DP로 풀어야 한다..

 

T의 범위가 어디까지인지 잘 모르겠지만 시간 제한이 0.25초이고 DP를 통해 값을 저장하지 않으면 재귀 호출에 의해 중복 계산이 생겨 최악의 경우 O(2^40) ≈ O(1,099,511,627,776)의 시간 복잡도가 발생한다.

 

따라서 DP 테이블을 만들어서 이전 숫자들의 0과 1의 출력 횟수 정보들을 저장해서 가져오는 방식으로 풀어야 할 것 같다.

 

정답

import java.io.*;
import java.util.*;

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 T = Integer.parseInt(br.readLine());
        Map<Integer, int[]> dpMap = new HashMap<>();

        int[] fib0Arr = {1, 0};
        int[] fib1Arr = {0, 1};

        dpMap.put(0, fib0Arr);
        dpMap.put(1, fib1Arr);

        for (int i=2; i<=40; i++) {
            int[] inputArr = {dpMap.get(i-1)[0] + dpMap.get(i-2)[0], dpMap.get(i-1)[1] + dpMap.get(i-2)[1]};
            dpMap.put(i, inputArr);
        }

        for (int i=0; i<T; i++) {
            int num = Integer.parseInt(br.readLine());
            bw.write(dpMap.get(num)[0] + " " + dpMap.get(num)[1] + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

풀이

1. 우선 fibonacci(0)과 fibonacci(1)은 각각 1 0과 0 1이 출력임을 알 수 있다.

        int[] fib0Arr = {1, 0}; // fibonacci(0) : 1 0
        int[] fib1Arr = {0, 1}; // fibonacci(1) : 0 1

        dpMap.put(0, fib0Arr); // 0번 key에 {1, 0} 넣기
        dpMap.put(1, fib1Arr); // 1번 key에 {0, 1} 넣기

 

2. 그 이후 값들은 n-1과 n-2로 불러오면 되므로 for문을 통해 갱신한다.

        for (int i=2; i<=40; i++) { // 2부터 40까지 dp테이블 채우기
                int[] inputArr = {dpMap.get(i-1)[0] + dpMap.get(i-2)[0], dpMap.get(i-1)[1] + dpMap.get(i-2)[1]};
                // dpMap.get(i-1)[0] + dpMap.get(i-2)[0] : i-1과 i-2의 0 출력 횟수 더하기
                // dpMap.get(i-1)[1] + dpMap.get(i-2)[1] : i-1과 i-2의 1 출력 횟수 더하기
                dpMap.put(i, inputArr); // i key에 새로 갱신한 0과 1의 출력 횟수 넣기
            }

 

3. 각 테스트 케이스마다 dpMap에서 N에 해당하는 key값만 가져와서 0과 1의 출력 횟수만 가져오면 된다.

        for (int i=0; i<N; i++) {
                int num = Integer.parseInt(br.readLine()); // dpMap에서 찾을 key값
                bw.write(dpMap.get(num)[0] + " " + dpMap.get(num)[1] + "\n");
                // dpMap.get(num)[0] : 0 출력 횟수
                // dpMap.get(num)[1] : 1 출력 횟수
            }