[백준] S3 1788번 피보나치 수의 확장 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1788번: 피보나치 수의 확장

[문제] 

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

[입력]

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

[출력]

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

[풀이]

1. 값을 입력받아 준다.

2. 입력받은 값을 1000000을 더해준다.

3. 음수일 경우와  짝수의 경우를 나눠 dp 배열을 채워준다.

4. 음수, 양수에 따른 결과를 출력한다.

5. 절댓값을 출력한다.

[접근]

1. 피보나치 문제를 풀듯 풀면 되겠다고 생각하였다.
2. 배열에 담기 위해 기준점을 절댓값의 범위인 1000000으로 잡고 계산한다.

[코드]

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

public class Main {
	static long mod = 1000000000;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 100만을 더해서 기준을 100만으로 잡아준다.
		int n = Integer.parseInt(br.readLine()) + 1000000;
                long[] dp = new long[2000001];

                // 0 위치
                dp[1000000] = 0;
                // 1 위치
                dp[1000001] = 1;

                // 음수일 때
                if (n < 1000000) {
                    for (int i = 999999; i >= n; i--) {
                        // 점화식 : dp[i + 2] - dp[i + 1]
                        dp[i] = (dp[i + 2] - dp[i + 1]) % mod;
                    }
                }
                // 짝수일 때
                else {
                    for (int i = 1000002; i <= n; i++) {
                        // 점화식 : dp[i - 1] + dp[i - 2]
                        dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
                    }
                }

                // 0일 때
                if (dp[n] == 0)
                    System.out.println("0");
                // 양수일 때
                else if (dp[n] > 0)
                    System.out.println("1");
                // 음수일 때
                else
                    System.out.println("-1");

                System.out.println(Math.abs(dp[n]));
	}
}