피보나치 수 2

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	16497	5646	4823	39.407%

문제

피보나치 수는 0과 1로 시작한다.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.

그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 F_n = F_n-1 + F_n-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다.

n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

출처

• 문제를 만든 사람: baekjoon

비슷한 문제

• 2747번. 피보나치 수
• 2748번. 피보나치 수 2
• 2749번. 피보나치 수 3
• 10870번. 피보나치 수 5

알고리즘 분류

• 다이나믹 프로그래밍
• 임의 정밀도 / 큰 수 연산

---

n은 10,000보다 작거나 같은 자연수 또는 0으로

만약 n이 10,000이라면 결과 값은 아래와 같다.

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

연산중에 오버플로가 발생하며

재귀로 접근하면 시간 초과 문제가 생긴다.

따라서 string을 이용한 덧셈 연산 / DP를 사용해야 한다.

(전에 풀었던 아래의 두 문제를 조합하여 해결했다. )

백준 15353번 (큰 수 A+B (2), C++, 큰 수 연산) [BAEKJOON]

백준 2748번 (피보나치 수 2, C++, DP) [BAEKJOON]

---

통과된 코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;

string arr[10001];

// 두 문자열을 더해주는 함수
string SumString(string strA, string strB)
{
	string tempStr;

	// 두 문자열 중에서 가장 높은 인덱스 길이 찾음
	int maxLength = strA.length() > strB.length() ? strA.length() : strB.length();

	// 문자열을 뒤집어 준다.
	reverse(strA.begin(), strA.end()); 
	reverse(strB.begin(), strB.end());

	// 뒤집은 두 문자열의 인덱스를 맞추어 준다.
	for (int i = strA.length(); i < maxLength; i++) { strA.push_back('0'); }
	for (int i = strB.length(); i < maxLength; i++) { strB.push_back('0'); }

	int tempOne, tempTwo, tempThree;
	int up = 0; 

	// 같은 인덱스의 char를 int로 변환하고 서로 더 해준다.
	// 만약 up 변수로 올림 처리를 해준다.
	for (int i = 0; i < maxLength; i++) {
		tempOne = 0;
		tempTwo = 0;
		if (i <= strA.length()) { tempOne = strA[i] - '0'; } // char => int
		if (i <= strB.length()) { tempTwo = strB[i] - '0'; } // char => int
		tempThree = tempOne + tempTwo + up;
		up = 0;

		if (tempThree >= 10) {
			tempThree -= 10;
			up += 1; // 올림처리
		}

		tempStr.push_back(tempThree + '0'); // int => char
	}

	if (up >= 1) { tempStr.push_back('1'); } // 올림이 남아있다면
	reverse(tempStr.begin(), tempStr.end()); // 더한 값을 뒤집어 준다.
	return tempStr;
}

string FibonacciDP(int N)
{
	arr[0] = "0";
	arr[1] = "1";

	for (int i = 2; i <= N; i++) {
		arr[i] = SumString(arr[i - 1], arr[i - 2]);
	}

	return arr[N];
}

int main()
{
	cin >> N;
	cout << FibonacciDP(N);
	return 0;
}

arr의 범위를 10,000으로 설정하여 런타임 에러가 발생했음.

전에 풀었던 문제의 코드들을 조합해서 해결해서 크게 어렵지 않았다.

https://www.acmicpc.net/blog/view/28 <- 피보나치 수를 구하는 여러가지 방법