[Baekjoon] 피보나치 수의 확장(BOJ 1788)

👀 문제 설명

문제

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

 

예제 입력 1

-2

 

예제 출력 1

-1

1

✍🏻풀이

먼저, 음수일 때의 피보나치 값을 구해봤다.

n	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7
F(n)	13	-8	5	-3	2	-1	1	0	1	1	2	3	5	8	13

위 표를 보면 n이 음수일 때 F(n)의 규칙을 구할 수 있다.

 

규칙

1. n이 음수일 때 F(n)의 절대값은 n이 양수일 때의 F(n)과 같다.

2. n이 -2, -4, -6,• • 일 때 F(n) = -(F(-n))

3. n이 -1, -3, -5, • • 일 때 F(n) = F(-n))

 

이 규칙을 사용하여 프로그램을 작성하면 된다.

 

그런데 코드에 의문점이 생겼당 .. 이건 아직 해결을 못해서 딴 애들은 어떻게 풀었는지 물어보고 고쳐야지..!

 

상수 선언

#define MOD 1000000000 : 절대값을 1000000000으로 나눈 나머지를 출력하기 위한 값

 

필요한 변수

int fibonacci[1000001] : 피보나치 값을 저장할 배열

 

알고리즘

1. for문을 돌려 1000000까지의 피보나치 값을 fibonacci[i]에 넣어둔다.

2. 음수일 때 위 규칙2와 규칙3을 적용하여 피보나치 값을 구한다.

3. 구한 fibonacci값에 MOD를 나눈 나머지 값을 출력한다.

 

코드

//
//  BOJ_1788.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/07/13.
//  Copyright © 2020 조수민. All rights reserved.
//
//  피보나치 수의 확장(https://www.acmicpc.net/problem/1788)

#include <iostream>
#include <stdio.h>

#define MOD 1000000000

using namespace std;

int fibonacci[1000001];

int getFibonacci(int n)
{
    if (n == 0) // 0일 때
        return fibonacci[0];
    else if (n > 0) // 양수일 때
        return fibonacci[n];
    else // 음수일 때
    {
        if (n % 2 == 0) // 2로 나누어 떨어질 때 (절대값이 짝수일 때)
            return fibonacci[n * (-1)] * (-1);
        else // 2로 나누어 떨어지지 않을 때 (절대값이 홀수일 때)
            return fibonacci[n * (-1)];
    }
}

int main()
{
    int n;
    
    // fibonacci 배열에 양수일 때의 피보나치 값을 구해서 넣어둔다.
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    
    for (int i = 2; i <= 1000000; i++)
        fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % MOD; // 1) 여기서 MOD로 나눴는데
    
    cin >> n; // n을 입력받는다.
    
    // 출력
    if (n > 0) // n이 양수일 때
        cout << 1 << endl;
    else if (n == 0) // n이 0일 때
        cout << 0 << endl;
    else // n이 음수일 때
    {
        if (n % 2 == 0) // n이 2로 나누어 떨어지면 피보나치 값이 음수이다.
            cout << -1 << endl;
        else // n이 2로 나누어 떨어지지 않으면 피보나치 값이 양수이다.
            cout << 1 << endl;
    }
    cout << fibonacci[abs(n)] % MOD << endl; // 2) 왜 여기서 MOD로 또 나누지..?
    
        
    return 0;
}

// 이게 맞는 답인데 의문점 1 & 2