[백준] 1003 피보나치 함수 - 자바

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

1003번: 피보나치 함수

문제 풀이

문제를 풀기 전에 항상 조건을 먼저 보자.
시간 제한이 0.25초로 값의 범위는 40이하이다. 만약 단순히 재귀로 풀게 되면 40의 값이 들어올 때 무수히 많은 연산으로 시간초과가 발생할 것이다.

그래서 이 문제는 dp를 이용해야 한다.

항상 dp를 이용해서 풀 때 작은 수의 샘플로 공식을 찾는 습관을 들이자
딱 값만 보고선 dp를 이용하기 매우 힘들다.

fibo(3)을 얻기 위해선 fibo(2)+fibo(1)을 해야 한다는 것을 알 것이다.
그렇다면 fibo(0)과 fibo(1)이 호출된 순서는 어떤 연관이 있을까?

이미 해보신 분을 알 거다. 피보나치 공식과 똑같다.
fibo(3)에서 fibo(0)과 fibo(1)이 호출된 횟수는 fibo(2)에서 fibo(0)과 fibo(1) 호출된 횟수 + fibo(1)에서 fibo(0)과 fibo(1)이 호출된 횟수이다.

글로 보니까 힘들다면 바로 코드를 보자

코드

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

class pair {
    int zero; // fibo(0)이 호출된 횟수
    int one; // fibo(1)이 호출된 횟수

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

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

        int n = Integer.parseInt(br.readLine());

        int[] input = br.lines().limit(n).mapToInt(Integer::parseInt).toArray();

        // 입력되는 수의 범위가 40까지 이므로
        pair[] dp = new pair[41];
        // 디폴트 값
        dp[0] = new pair(1, 0);
        dp[1] = new pair(0, 1);
        // i의 0과 1이 호출된 횟수는 i-1과 i-2에서 호출된 0의 합, 1의 합과 같다.
        for (int i = 2; i<=40; i++) {
            pair prev1 = dp[i - 1];
            pair prev2 = dp[i - 2];
            dp[i] = new pair(prev1.zero+ prev2.zero, prev1.one+ prev2.one);
        }

        Arrays.stream(input).forEach(i -> System.out.println(dp[i].zero+" "+dp[i].one));

    }
}

 

자세한 설명은 주석으로 작성해놓았다. 참고하길 바란다.