[Java] 1788번: 피보나치 수의 확장 Silver 3

문제 링크

이 문제는 DP 문제라기보다는 그냥 구현 문제 느낌이었다.

문제에서 수식이 다 있고, 그것대로 작성만 하면 답이 나왔다.. ㅇㅅㅇ

우리는 음수인 N에 대한 피보나치 수를 구해야 한다.
기존 피보나치수열의 점화식은 N이 증가하는 방향으로 정의되어 있다.
여기서 N이 감소하는 방향으로 바꿔주기만 하면 된다.
즉,

F[N] = F[N-1] + F[N-2] 여기서 F[N-1]을 좌변으로 이동시켜서
F[N-2] = F[N] - F[N-1] 로 바꾸고 다시 각 N에 N+2를 넣어서
F[N] = F[N+2] - F[N+1] 로 바꿔준다.

근데 음수 인덱스 배열은 생성할 수 없기에 이것을 음수 기준으로 반전시켜주면 된다.

그러면 최종적으로 점화식이 완성된다.
f[N] = F[N-2] - F[N-1]

정답

그치만.. 예외처리와 음수 양수 플래그 출력, 절대값 출력 때문에 조금 귀찮은 문제다..

import java.io.*;

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

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        if (N > 0) {
            int[] dp = new int[N + 1];
            dp[1] = 1;
            for (int i = 2; i <= N; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000000;
            }
            if (dp[N] > 0) {
                System.out.println(1);
            } else if (dp[N] < 0) {
                System.out.println(-1);
            } else {
                System.out.println(0);
            }
            System.out.println(Math.abs(dp[N]));
        } else if (N < 0) {
            int[] dp = new int[-N + 1];
            dp[1] = 1;
            for (int i = 2; i <= -N; i++) {
                dp[i] = (dp[i - 2] - dp[i - 1]) % 1000000000;
            }
            if (dp[-N] > 0) {
                System.out.println(1);
            } else if (dp[-N] < 0) {
                System.out.println(-1);
            } else {
                System.out.println(0);
            }
            System.out.println(Math.abs(dp[-N]));
        } else {
            System.out.println(0);
            System.out.println(0);
        }
    }
}