백준 1788. 피보나치 수열 확장

지난번에 한번 다룬적이 있던 피보나치 수열문제의 확장판 문제입니다 :)

 

 

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

1788번: 피보나치 수의 확장

https://youtu.be/zFJN03V-iBA

 

 

 

세상에 영원한 것은 없습니다.

지극히 높으신 신께서 사람을 감동케 하셔서 쓰신 성서에는 다음과 같이 말씀이 씌어져 있습니다.

 

사랑은 언제까지나 떨어지지 아니하되

예언도 폐하고 방언도 그치고 지식도 폐하리라

우리는 부분적으로 알고 부분적으로 예언하니

온전한 것이 올 때에는 부분적으로 하던 것이 폐하리라

성서 고린도전서 13장 8절 ~ 10절

 

우리가 배운 수학에서는 무한대라는 용어가 있습니다.

집합과 수열, 무한 소수 등 영원할 것 같은 수학도

어쩌면 인간의 지식의 한 부분인데요.

​

하나님께서는 마지막 날에 지식도 폐하신다고 하시는 것으로 보면,

수학이라는 학문 자체도 어찌 보면 영원하지 않을지도 모릅니다 :)

​

음의 피보나치 수열이라고 들어보셨나요?

음의 피보나치 수열은 아래와 같습니다.

​

0, 1, -1, 2, -3, 5. -8, 13, ...

​

양의 피보나치 수열과 순서는 똑같습니다만,

짝수번째는 음수, 홀수번째는 양수가 됩니다.

​

n번째 피보나치를 F(n) 이라고 표현할 때,

F(-2) = -1, F(-3) =2가 되는 것이지요.

​

음의 피보나치를 사실 굳이 구할 필요는 없습니다.

양의 피보나치 수열에 해당하는 값 구해놓고서

구할 피보나치 n 값이 음수이고, 짝수라면 마이너스 수치로 표현만 해주면 그만이지요.

​

소스에 주석을 달아드리는게 더 나을듯 해서 설명은 이쯤하고 소스 공개합니다.

언제나 더 좋은 소스는 나올 수 있으며 그 소스는 여러분의 몫입니다. :)

 

#include <iostream>

void Result()
{
	// n값을 입력받습니다.
	long long n;
	scanf("%lld", &n);

	// n값이 0일 경우 예외적으로 먼저 출력하고 끝내버리면,
	// 생각할 경우의 수가 줄어듭니다.
	if(n==0){ printf("0\n0\n"); return; }

	// 원래 n 값이 양수인지 음수인지 여부 저장하고
	// n값이 음수일 때 양수로 바꿔서 계산하기 위함입니다.
	bool plus=true;

	// N값이 음수라면 
	if(n<0){

		// 양수로 바꿉니다.
		n=-n;

		// 그리고 원래값이 음수였다고 저장합니다.
		plus=false;
	}
	
	// 숫자1, 2, 임시저장변수를 정의하고
	long long a=0, b=1, tmp;

	// 2부터 N까지 반복합니다.
	for(long long i=2;i<=n;++i)
	{
		// 임시저장소에 숫자2 저장
		tmp=b;

		// 숫자2를 숫자1 + 숫자2로 바꿉니다.
		// 그리고 수가 초과됨을 방지하기 위해 문제에 제시된대로 1,000,000,000 으로 나눈 나머지만 저장합니다.
		b=(a+b) % 1000000000;

		// 숫자1을 원래 숫자2 값으로 바꿔줍니다.
		a=tmp;
	}

	// N번째를 모두 반복했다면,
	// 원래 n이 음수이고 짝수인 경우만 첫번째 줄에 -1 출력
	if(plus==false && n%2==0)printf("-1\n");
	// 그 외는 첫번째 줄에 1출력
	else printf("1\n");

	// n팩토리얼의 절대값을 출력합니다.
	// 어차피 양수니까 절대값이나 마찬가지인 셈입니다.
	printf("%lld\n", b);
}

int main()
{
    Result();
}