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

피보나치 수 2

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초256 MB164975646482339.407%

문제

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

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

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

이를 식으로 써보면 Fn = Fn-1 + Fn-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

출처

비슷한 문제

알고리즘 분류


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

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

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

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

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

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

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


통과된 코드

#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 <- 피보나치 수를 구하는 여러가지 방법

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

위로 스크롤