[백준] 1788번 : 피보나치 수의 확장 – JAVA [자바]

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

1788번: 피보나치 수의 확장

 

---

• 문제

 

 

---

• 문제 풀이

백준 1788번 피보나치 수의 확장은 DP, 그중에서도 피보나치를 이용해서 푸는 문제이다. 이 문제의 조금 다른 점은 바로 피보나치의 확장, 즉 음수 n이 주어졌을 때도 이 음수 n의 피보나치 값을 구해야 한다는 것이다.

 

이 문제는 그렇게 어렵지 않다. 일반 피보나치와 거의 똑같은 문제이다. 피보나치는 다음과 같다

F(0) = 0

F(1) = 1;

F(n) = F(n-2) + F(n-1) , n > 1

 

이 점화식은 n이 2이상일때만 성립하는 점화식이다. 그래서 이번 문제에서는 이 점화식이 n ≤ 1 일때도 성립하게만 하면 된다. 즉, 다음과 같이 점화식을 바꾸면 된다.

 

F(n) = F(n+2) - F(n-1)  , n < 0

 

이렇게 점화식을 바꾸면 n이 음수일 때도 피보나치 수를 구할 수 있다.

 

한번 범위 -5 ≤ n ≤ 5 의 피보나치 수들을 구해보겠다.

우선 F(0) = 0, F(1) = 1 이므로 다음과 같이 테이블을 만들 수 있다.

 

그리고 n이 양수일 때 F(n) = F(n-2) + F(n-1) 이므로 양수인 n값들로 테이블을 채워보겠다.

n = 2 : F(2) = F(1) + F(0) = 1 + 0 = 1

n = 3 : F(3) = F(2) + F(1) = 1 + 1 = 2

n = 4 : F(4) = F(3) + F(2) = 2 + 1 = 3

n = 5 : F(5) = F(4) + F(3) = 3 + 2 = 5

 

 

이제 음수 n의 피보나치 수들을 채워보겠다.

n = -1 : F(-1) = F(1) - F(0) = 1 - 0 = 1

n = -2 : F(-2) = F(0) - F(-1) = 0 - 1 = -1

n = -3 : F(-3) = F(-1) - F(-2) = 1 - (-1) = 2

n = -4 : F(-4) = F(-2) - F(-3) = -1 - 2 = -3

n = -5 : F(-5) = F(-3) - F(-4) = 2 - (-3) = 5

 

 

DP 테이블은 -1,000,000 부터 1,000,000까지의 n의 피보나치 수를 포함해야 한다. 

따라서 DP 테이블의 크기는 2,000,001로 하고 n을 입력받을때 +1,000,000 해서 입력을 받는다. 그리고 DP 테이블의 기준을 dp [1,000,000]으로 잡는다. 즉 dp [999999] = dp [-1]과 같고 dp [1,000,001] = dp [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));
        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]));
    }
}

 

---

• 후기

이 문제를 이해만 했다면 쉽게 풀 수 있는 문제였을 것이다.