문제
구간 [a, b]에 포함되는 피보나치 수의 개수를 구하라. 수가 매우 클 수 있다.
입력
여러 테스트 케이스에 a와 b가 문자열로 주어지며, 둘 다 0이면 종료한다.
출력
각 케이스마다 구간 내 피보나치 수의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 100 0 0 | 5 |
풀이
큰 수 덧셈을 구현하여 피보나치 수를 생성하며, 범위 내 포함 여부를 센다.
- 문자열 비교 함수로 대소 비교를 수행한다 (길이 우선, 같으면 사전순)
- 피보나치 수를 문자열 덧셈으로 생성하며 b 이하인 동안 반복한다
- 각 피보나치 수가
[a, b]범위에 속하면 카운트를 증가시킨다
핵심 아이디어: 피보나치 수의 성장률이 지수적이므로 범위 내 피보나치 수의 개수는 적다. 큰 수 연산을 문자열로 처리하여 오버플로를 방지한다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(const string &a, const string &b)
{
if (a.size() != b.size())
return a.size() < b.size();
return a <= b;
}
string add(const string &x, const string &y)
{
string res;
int carry = 0;
int i = x.size() - 1, j = y.size() - 1;
while (i >= 0 || j >= 0 || carry)
{
int sum = carry;
if (i >= 0)
sum += x[i--] - '0';
if (j >= 0)
sum += y[j--] - '0';
res += sum % 10 + '0';
carry = sum / 10;
}
reverse(res.begin(), res.end());
return res;
}
int main()
{
while (true)
{
string a, b;
cin >> a >> b;
if (a == "0" && b == "0")
break;
string x = "1", y = "2";
int cnt = 0;
while (cmp(x, b))
{
if (cmp(a, x))
cnt++;
string tmp = x;
x = y;
y = add(tmp, y);
}
cout << cnt << '\n';
}
return 0;
}복잡도
- 시간: O(F * D) (F: b까지의 피보나치 수 개수, D: 자릿수)
- 공간: O(D)