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

 

 

 

백준 1788번

 

 

 

 

www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

 

 

---

백준 1788번
피보나치 수의 확장

---

 

제목 그대로 피보나치 수를 확장하여 만든 문제입니다.

문제에서 요구하는 대로 손으로 수를 적어보니, 0을 기준으로 음수와 양수 인덱스 값이 대칭을 이루더라고요.

 

F(3) = 2

F(2) = 1

F(1) = 1

F(0) = 0

F(-1) = 1

F(-2) = -1

F(-3) = 2

F(-4) = -1

 

단, 음수쪽 인덱스에서는 절대값이 짝수면 음수였습니다.

이런 점을 코드에 그대로 구현하면, for문 하나로 풀 수 있습니다.

따로 적용된 알고리즘 기법은 없고, 단순 구현으로 풀었답니다.

 

#include <iostream>
#define mod 1000000000
using namespace std;

int dp[1000001]={0,1,0};

int main(){
    int input;
    int index;
    cin >> input;
    if(input<0)
    {
        index = input *(-1);
    }
    else
    {
        index = input;
    }
    if(index == 0 )
    {
        cout << 0;
        cout << "\n";
        cout << 0;
        return 0;
    }
    for(int i = 2; i <= index; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % mod;
    }
    dp[index] = dp[index] % mod;
    if(input < 0)//음수의 경우
    {
        if(index % 2 == 0)// 절대값이 짝수인 경우
        {
            cout << -1;
            cout << "\n";
            cout << dp[index];
            return 0;
        }
    }
    //그 외
    cout << 1;
    cout << "\n";
    cout << dp[index];
    

    return 0;
}

 

뭔가 더 좋은 방법이 있을 것도 같은 데, 생각나는 게 없네요....