[BOJ / C++] 1788번 : 피보나치 수의 확장

문제

 F(n):={0if n=0;1if n=1;F(n−1)+F(n−2)if n>1.$$F(n) := \begin{cases}0 & \text{if }n = 0\text{;} \\ 1 & \text{if }n = 1\text{;} \\ F(n-1) + F(n-2) & \text{if }n > 1\text{.} \end{cases}$$ 

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 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으로 나눈 나머지를 출력한다.

Solved.ac 레벨

실버 III

풀이

#include <bits/stdc++.h>
#define MAX 1000000 + 1

using namespace std;

int n;
int result;
long long dp[MAX];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    
    if(n > 0){
        result = 1;
    }else if(n < 0){
        if(abs(n) % 2 == 0) result = -1;
        else result = 1;
    }
    else result = 0;

    dp[0] = 0;
    dp[1] = 1;

    n = abs(n);

    for(int i = 2; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000000;
    }

    cout << result << '\n' << dp[n];

    return 0;
}

dp[-3] 까지만 보면 대충, n이 음수이면서 절대값이 음수면 f(n)의 값이 양수, n이 음수이면서 절대값이 양수면 음수인 것을 알 수가 있고, n이 양수일 때와 0을 기준으로 대칭을 이루는 것을 알 수 있다. 따라서 f(n)의 값의 양수, 음수 여부만 n을 통해 가려주고 dp 배열은 기존 피보나치 함수의 점화식을 그대로 사용하면 된다. 

 

또한 1,000,000,000을 나눈 나머지를 저장해야 하므로, dp 배열의 자료형에 주의하자.

 

1788번: 피보나치 수의 확장