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

문제링크 : https://www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000000;
int dp[1000001];
int sign=1;
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;
    if(N<0) 
    {
        N*=-1;
        if(N%2==0) sign=-1; //N이 짝수일때만 음수
    }
    if(N==0) sign=0;

    dp[0]=0; dp[1]=1;
    for(int i=2; i<=N; i++)
    {
        dp[i] = (dp[i-1]+dp[i-2])%MOD;
    }
    cout << sign << "\n" <<dp[N];
    return 0;
}

흔히 알고 있는 피보차니 수열에 음수까지 확장된 문제이다.

우선 음수일 때 케이스를 보면 다음과 같다.

 

F[i] = F[i-1] + F[i-2];
-> F[i-2] = F[i] - F[i-1];

F[-1] = F[1] - F[0] -> 1
F[-2] = F[0] - F[-1] -> -1
F[-3] = F[-1] - F[-2] -> 2
F[-4] = F[-2] - F[-3] -> -3

보면 N의 절대값이 짝수일 때 음수가 나오는 것을 볼 수 있다.

따라서 부호를 출력하기 위한 변수 sign을 abs(N)이 짝수일 경우에 -1로 저장해준다.

그리고 문제에서 N==0 일때는 0을 출력하도록 명시했다.

이 경우에 sign을 0으로 저장하고 2가지 케이스 이외에는 1이므로 처음에 1로 선언하고 시작했다.

 

이외에는 흔히아는 피보나치 수열 점화식을 그대로 작성하면 된다.