[백준] 1788번 - 피보나치 수의 확장 [Java]

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

 

[백준] 1788번 - 피보나치 수의 확장 [Java]

[백준] 1788번 - 피보나치 수의 확장 [Java]

---

1.  아이디어

 

N이 0일 때 양수일 때, 음수일 때를 나눠서 해결했다.

---

2. 문제풀이

 

N이 0일 경우 0 두개를 출력하고 종료했고 N이 양수일 경우 일반적인 다이나믹 프로그래밍을 활용한 피보나치 구현으로, N이 음수일 경우 이항을 통해 점화식을 구해서 동일하게 다이나믹 프로그래밍으로 해결했다. N이 음수일 경우 필요에 따라 절댓값으로 양수처리를 해줘야 한다.

---

3. 코드

 

import java.io.*;

public class Main {

    private static final int MOD = 1_000_000_000;

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

        int N = Integer.parseInt(br.readLine());
        if (N == 0) {
            System.out.println(0);
            System.out.println(0);
            return;
        }

        int[] dp = new int[1 + Math.abs(N)];
        dp[1] = 1;

        if (N >= 0) {
            for (int i = 2; i <= N; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
            }
        } else {
            for (int i = 2; i <= -N; i++) {
                dp[i] = (dp[i - 2] - dp[i - 1]) % MOD;
            }
        }

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

---

4. 후기