백준 15624번 피보나치 수 7 C++ 구현해보기

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

// 복잡도 O(str1Len + str2Len)
std::string AddBigNum(std::string str1, std::string str2)
{
	int32_t str1Len = str1.length();
	int32_t str2Len = str2.length();

	if (str1Len > str2Len)
	{
		std::swap(str1, str2);
		std::swap(str1Len, str2Len);
	}

	std::reverse(str1.begin(), str1.end());
	std::reverse(str2.begin(), str2.end());

	std::string retStr = "";

	int32_t carry = 0;
	for (int32_t i = 0; i < str1Len; i++)
	{
		int32_t tempSum = (str1[i] - '0') + (str2[i] - '0') + carry;
		retStr.push_back(tempSum % 10 + '0');
		carry = tempSum / 10;
	}

	for (int32_t i = str1Len; i < str2Len; i++)
	{
		int32_t tempSum = (str2[i] - '0') + carry;
		retStr.push_back(tempSum % 10 + '0');
		carry = tempSum / 10;
	}

	if (carry != 0)
	{
		retStr.push_back(carry + '0');
	}

	std::reverse(retStr.begin(), retStr.end());

	return retStr;
}

int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t num;
	std::cin >> num;
	std::cin.ignore();

	static std::array<std::string, 10001> fibArr;
	//fibArr.fill(-1);
	fibArr[0] = "0";
	fibArr[1] = "1";

	for (int i = 2; i <= num; i++)
	{
		fibArr[i] = AddBigNum(fibArr[i - 1], fibArr[i - 2]);
		//std::cout << fibArr[i] << "\n";
	}

	std::cout << fibArr[num];
	//for (int i = 0; i < 10; i++)
	//{
	//	std::cout << fibArr[i] << "\n";
	//}
}​

---

```

백준 15624번 피보나치 수 7 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 15624번 풀이

---

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

15624번: 피보나치 수 7

 

 

 

백준 15624번 피보나치 수 7은

난이도 브론즈 등급의 문제로서

 

피보나치 수

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

가 주어질 때

( 피보나치 수는 1번째 수는 0, 2번째 수는 1이고 그다음 숫자부터 전 숫자와 전전 숫자의 합을 적는 수)

(예

1 = 0 + 1,

2 = 1 + 1,

3 = 1 + 2....)

 

1,000,000보다 작거나 같은 자연수 또는 0이 n 값으로 주어 질 때

n번째 피보나치수를 1,000,000,007으로 나눠서 출력하면 되는 문제입니다.

 

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

1,000,000 개의 숫자를 저장하는 배열을 선언하고

 

첫 번째 수와 두 번째 수만 지정해준 다음

 

for문을 돌면서

 

피보나치 수를 n번째 까지 전부 계산하면서 모듈러 연산을 해주고

 

답을 출력해주면 되는 문제이며

 

전체 코드는 아래와 같습니다.

 

 

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>



int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t num;
	std::cin >> num;
	std::cin.ignore();

	static std::array<int64_t, 1000001> fibArr;
	//fibArr.fill(-1);
	fibArr[0] = 0;
	fibArr[1] = 1;

	for (int i = 2; i <= num; i++)
	{
		fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]) % 1000000007;
	}

	std::cout << fibArr[num];
	//for (int i = 0; i < 10; i++)
	//{
	//	std::cout << fibArr[i] << "\n";
	//}
}

 

 

연관문제의 경우

 

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

2747번: 피보나치 수

 

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

2748번: 피보나치 수 2

 

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

2749번: 피보나치 수 3

// 2749

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

// Pisano Period 참조

int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int64_t num;
	std::cin >> num;
	std::cin.ignore();

	static std::array<int64_t, 1500001> fibArr;
	//fibArr.fill(-1);
	fibArr[0] = 0;
	fibArr[1] = 1;

	num = num % 1500000;

	for (int i = 2; i <= num; i++)
	{
		fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]) % 1000000;
		//std::cout << fibArr[i] << "\n";
	}

	std::cout << fibArr[num];
	//for (int i = 0; i < 10; i++)
	//{
	//	std::cout << fibArr[i] << "\n";
	//}
}

 

 

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

10826번: 피보나치 수 4

 

// 10826

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

// 복잡도 O(str1Len + str2Len)
std::string AddBigNum(std::string str1, std::string str2)
{
	int32_t str1Len = str1.length();
	int32_t str2Len = str2.length();

	if (str1Len > str2Len)
	{
		std::swap(str1, str2);
		std::swap(str1Len, str2Len);
	}

	std::reverse(str1.begin(), str1.end());
	std::reverse(str2.begin(), str2.end());

	std::string retStr = "";

	int32_t carry = 0;
	for (int32_t i = 0; i < str1Len; i++)
	{
		int32_t tempSum = (str1[i] - '0') + (str2[i] - '0') + carry;
		retStr.push_back(tempSum % 10 + '0');
		carry = tempSum / 10;
	}

	for (int32_t i = str1Len; i < str2Len; i++)
	{
		int32_t tempSum = (str2[i] - '0') + carry;
		retStr.push_back(tempSum % 10 + '0');
		carry = tempSum / 10;
	}

	if (carry != 0)
	{
		retStr.push_back(carry + '0');
	}

	std::reverse(retStr.begin(), retStr.end());

	return retStr;
}

int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t num;
	std::cin >> num;
	std::cin.ignore();

	static std::array<std::string, 10001> fibArr;
	//fibArr.fill(-1);
	fibArr[0] = "0";
	fibArr[1] = "1";

	for (int i = 2; i <= num; i++)
	{
		fibArr[i] = AddBigNum(fibArr[i - 1], fibArr[i - 2]);
		//std::cout << fibArr[i] << "\n";
	}

	std::cout << fibArr[num];
	//for (int i = 0; i < 10; i++)
	//{
	//	std::cout << fibArr[i] << "\n";
	//}
}

 

 

 

 

 

 

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

10870번: 피보나치 수 5

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

11444번: 피보나치 수 6

가 있으며 위에 문제를 푸셨다면 나머지 문제도 쉽게 푸실 수 있으실 겁니다

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---