문제
N이 주어졌을 때 N번째 피보나치 수를 출력하라. N이 최대 10000이므로 결과가 매우 큰 수가 될 수 있다.
입력
정수 N이 주어진다 (0 이상 10000 이하).
출력
N번째 피보나치 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
35 | 9227465 |
풀이
피보나치 수가 정수형 범위를 초과하므로 문자열 기반 큰 수 덧셈을 구현한다.
- 큰 수 덧셈 함수를 구현한다: 두 문자열을 뒤집어 자릿수별로 더하고 올림을 처리한다
a = "0",b = "1"로 시작한다- 2부터 N까지 반복하며
result = sum(a, b)를 계산하고a = b,b = result로 갱신한다 - N번째 피보나치 수를 출력한다
핵심 아이디어: C++에는 파이썬처럼 큰 수 지원이 없으므로, 문자열 덧셈을 직접 구현하여 자릿수가 2000자리 이상인 피보나치 수를 다룬다.
코드
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
string sum(string x, string y)
{
int num;
int carry = 0;
string result;
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
while (x.length() < y.length())
{
x += '0';
}
while (x.length() > y.length())
{
y += '0';
}
for (int i = 0; i < x.length(); ++i)
{
num = (x[i] - '0' + y[i] - '0' + carry) % 10;
result += to_string(num);
carry = (x[i] - '0' + y[i] - '0' + carry) / 10;
}
if (carry != 0)
{
result += to_string(carry);
}
reverse(result.begin(), result.end());
return result;
}
int main(int argc, char *argv[])
{
int n;
string a;
string b;
string result;
cin >> n;
a = '0';
b = '1';
if (n == 0)
{
result = "0";
}
if (n == 1)
{
result = "1";
}
for (int i = 2; i <= n; ++i)
{
result = sum(a, b);
a = b;
b = result;
}
cout << result << endl;
return 0;
}복잡도
- 시간: O(N * D) (D: 피보나치 수의 자릿수, 최대 약 2000자리)
- 공간: O(D)