[백준] 1788 : 피보나치 수의 확장 / JAVA, dp, 재귀, 피보나치 수열

// dp[10000000]를 0으로 두고 피보나치수를 찾습니다.
 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()) + 1000000;
        long[] dp = new long[2000001];
        dp[1000001] = 1;
        if (n < 1000000) {
            for (int i = 999999; i >= n; i--) {
                dp[i] = (dp[i+2] - dp[i+1]) % 1000000000;
            }
        } else {
            for (int i = 1000002; i <= n; i++) {
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000000;
            }
        }
        if (dp[n] > 0) System.out.println(1);
        if (dp[n] == 0) System.out.println(0);
        if (dp[n] < 0) System.out.println(-1);
        System.out.print(Math.abs(dp[n]));
    }​

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

public class Main {
	// main과 fibo 모두에서 쓰일 피보나치수열을 넣는 배열을 전역변수로 선언합니다.
	static int[] data = new int[1000001];
	
    // main : fibo를 호출하여 수열값을 구하고 문제의 조건을 만족시키는 연산을 수행합니다.
	public static void main(String[] args) throws NumberFormatException, IOException {
		// InputStreamReader로 시스템 입력값을 받는데 버퍼링을 통해 char를 line단위로 
        // 빠르게 받아올 수 있는 BufferedReader를 통해 입력 속도를 높입니다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n을 입력받아 int형으로 파싱합니다.
		int n = Integer.parseInt(br.readLine());
        // 첫번째 정답값을 가장 많은 경우의 수인 1로 초기화합니다.
		int ans1 = 1;
        // 두번째 정답값을 임의로 0으로 초기화합니다. 
		int ans2 = 0;
        // 함수 호출을 줄이기 위해 n의 절댓값을 N으로 선언합니다.
		int N = Math.abs(n);

		// 두번째 정답값을 얻기위해 fibo 메서드를 사용합니다.
        // f(n)의 절댓값 = f(-n)의 절댓값이기 때문에 양수 N의 f(N)을 구합니다. 
		ans2 = fibo(N);

		// 첫번째 정답값은 n이 양수/0/음수인지에 따라 달라지므로 if문 처리합니다.
        // n이 양수인경우 default인 1이 입력됩니다.
        // n이 0인 경우 0으로 입력합니다.
		if (n == 0)
			ans1 = 0;
        // n이 음수인경우 n이 짝수일때만 f(n)이 음수가 되므로 -1을 입력합니다.
		else if ((n < 0) && (N % 2 == 0))
			ans1 = -1;
		
        // 두개의 답을 출력합니다.
		System.out.println(ans1);
		System.out.println(ans2);
	}

	// 재귀로 피보나치수를 구하는 메서드를 정의합니다.
	private static int fibo(int N) {
		// N이 0 또는 1 일때는 피보나치 규칙이 발생하지 않아 예외처리 합니다.
        if (N < 2)
			return N;
        // f(n)을 백억자리 미만만 남깁니다.
		if (data[N] != 0)
			return data[N] % 1000000000;
            
        // 점화식에 의해 피보나치 수를 구해 백억자리 미만만 남깁니다.
		return data[N] = ((fibo(N - 1) + fibo(N - 2)) % 1000000000);
	}
}

21312번: 홀짝 칵테일