문제 풀이 방법
이 문제는 $F(n)$을 1000000000으로 나눈 나머지를 출력하면 되는 문제이기 때문에, 문자열로 할 필요없이 그냥 for문으로 해결할 수 있는 문제이다.
간단하게 for문 2개로 음수일때, 음수가 아닐때를 따져보면서 풀어보면 된다.
피보나치 수열 점화식
$n$이 음수일때의 피보나치 수열의 점화식은 $F(n) = F(n-2) - F(n-1)$으로 점화식을 새울 수 있다.
그래서 for문으로 다음과 같이 작성할 수 있다.
for (int i = 2; i <= abs(n); i++) {
a[i] = a[i - 2] - a[i - 1];
a[i] %= 1000000000;//long long 범위를 넘는 것을 방지하기 위해 처음부터 1000000000으로 나눔
}
$n$이 자연수일때는 $F(n) = F(n-1) + F(n-2)$으로 점화식을 새울 수 있다.
이 또한 for문으로 다음과 같이 작성할 수 있다.
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
a[i] %= 1000000000;//long long 범위를 넘는 것을 방지하기 위해 처음부터 1000000000으로 나눔
}
코드
C
#include <stdio.h>
#include <math.h>
using namespace std;
long long a[1000001], n;
int main() {
scanf("%d",&n);
a[0] = 0;
a[1] = 1;
if (n < 0) {
for (int i = 2; i <= abs(n); i++) {
a[i] = a[i - 2] - a[i - 1];
a[i] %= 1000000000;
}
if (a[abs(n)]<0)printf("-1\n");
## else printf("1\n");
printf("%lld",abs(a[abs(n)]) % 1000000000);
}
else if (n > 0) {
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
a[i] %= 1000000000;
}
printf("%lld",a[n] % 1000000000);
}
else printf("0\n0");
return 0;
}
C++
#include <iostream>
#include <math.h>
using namespace std;
long long a[1000001], n;
int main() {
cin >> n;
a[0] = 0;
a[1] = 1;
if (n < 0) {
for (int i = 2; i <= abs(n); i++) {
a[i] = a[i - 2] - a[i - 1];
a[i] %= 1000000000;
}
if (a[abs(n)]<0)cout << "-1" << "\n";
else cout << "1" << "\n";
cout << abs(a[abs(n)]) % 1000000000;
}
else if (n > 0) {
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
a[i] %= 1000000000;
}
cout << "1" << "\n" << a[n] % 1000000000;
}
else cout << "0" << "\n" << "0";
return 0;
}
다른 언어
다른 언어도 음수일때, 양수일때를 나눠 가며 각각 $F(n) = F(n-2) - F(n-1)$, $F(n) = F(n-1) + F(n-2)$ 점화식에 맞게 풀면 된다.