백준 - 피보나치 수의 확장 (C++)

Pixabay로부터 입수된 Karin Henseler님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

 

 이번 문제는 n에 대한 피보나치 수를 구하는 문제인데, 이 때 n이 음수일 수도 있다. 음수의 피보나치 수를 어떻게 구하는지에 대한 예시가 문제에 주어져 있다. 예를 들어 -1에 대한 피보나치 수, F(-1)을 구해보자. 이를 위해 잠시 1에 대한 피보나치 수 F(1)을 구하는 식을 생각해보자. F(1) = F(0) + F(-1)이므로 F(-1)은 F(1) - F(0) = 1 - 0 = 1이다. 즉, -1에 대한 피보나치 수 F(-1)은 1이다. 이런 방식으로 양수, 음수에 대한 피보나치 수를 계산해야 한다.

 

 양수에 대한 피보나치 수는 평소에 계산하던 대로 구하면 된다. 하지만 음수의 경우는 다르다. 

 

F(n) = F(n - 1) + F(n - 2)

 

이 삭에서 n이 -5라고 생각해보자. F(-5) = F(-6) + F(-7) 이기에 F(-6)과 F(-7)을 계산해야 한다. F(-6)은 F(-6) = F(-7) + F(-8) 이므로 F(-7)과 F(-8)을 계산해야 한다. 하지만 이 과정은 끝나지 않을 것이다. 왜냐하면 n이 0 이상일 경우, F(0)은 0, F(1)은 1처럼 정해진 끝이 있기에 n(양수)이 아무리 작아져도 0, 1에서 끝이 나지만 n이 음수일 경우는 미리 정해진 값이 없기 때문이다. 즉, 다른 방법을 생각해봐야 한다.

 

F(1) = F(0) + F(-1) ->  F(1) - F(0) = 1 - 0 = 1

 

 n이 음수일 때는 F(n)을 구하기 위한 n의 값이 계속 작아지는 것이 문제였다. 이를 해결하기 위해, F(-1)을 계산했던 방법을 응용할 것이다. F(-1)을 계산하기 위해 F(0)을 F(-1)의 반대로 넘겨주었다. (양변에 F(0)을 더했다.) 즉, 기존의 식을 아래처럼 변경할 수 있다.

 

F(n - 2) = F(n) - F(n - 1)

 

그 후, n에 k + 2라는 값을 대입하자.

 

F(k) = F(k + 2) - F(k + 1)

 

k에 대한 피보나치 수는 F(k + 2)에서 F(k + 1)을 뺀 수이다. 어찌 보면 당연한 얘기이다. 어쨌든, 이 식은 특정 수에 대한 피보나치 수를 계산하기 위해 k보다 큰 값의 수(에 대한 피보나치 수)를 필요로 한다. 그렇기에 F(-5)를 계산하기 위해서 F(-4), F(-3), F(-2), F(-1), F(0), F(1) 등이 필요하기에 F(-5)를 계산할 수 있다. 이를 적용한 코드는 다음과 같다.

 

#include <iostream>
#pragma warning(disable:4996)
#define MAX 1000001
#define MOD 1000000000
#define INIT -2000000000
using namespace std;

int N;
int positiveDp[MAX];
int negativeDp[MAX];

int Check(int num)
{
	int absNum = abs(num);

	if (num >= 0)
	{
		if (positiveDp[num] > INIT)
			return positiveDp[num];
	}
	else
	{
		if (negativeDp[absNum] > INIT)
			return negativeDp[absNum];
	}

	// 위에서 num == 0인 경우는 걸러진다.
	
	if (num > 0)
		return positiveDp[num] = (Check(num - 1) + Check(num - 2)) % MOD;
	else
		return negativeDp[absNum] = (Check(num + 2) - Check(num + 1)) % MOD;
		
	
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	cin.tie(0);

	for (int i = 0; i < MAX; ++i)
	{
		positiveDp[i] = INIT;
		negativeDp[i] = INIT;
	}

	positiveDp[0] = 0;
	positiveDp[1] = 1;
	positiveDp[2] = 1;

	negativeDp[0] = 0;
	negativeDp[1] = 1;

	cin >> N;	
    
    Check(N);
    
	int absN = abs(N);

	if (N >= 0)
	{
		if (positiveDp[N] > 0)
			cout << 1 << endl;
		else if (positiveDp[N] == 0)
			cout << 0 << endl;
		else
			cout << -1 << endl;
		
		cout << abs(positiveDp[N]) << endl;
	}
	else
	{
		if (negativeDp[absN] > 0)
			cout << 1 << endl;
		else if (negativeDp[absN] == 0)
			cout << 0 << endl;
		else
			cout << -1 << endl;
		
		cout << abs(negativeDp[absN]) << endl;
	}

    return 0;
}

 

 Check라는 함수에서 위의 식을 이용해 피보나치 수를 재귀적으로 구하고 있다. 그리고 positiveDp, negativeDp라는 배열은 각각 양수일 때의 피보나치 수와 음수일 때의 피보나치 수를 저장하는 배열이다. 둘을 구분한 이유는 배열의 인덱스로 음수는 불가능하기 때문이다. 그렇기에 음수에 대한 피보나치 수는 negativeDp[음수의 절댓값]에 저장했다.