[C++] 백준 4150번 피보나치 수

 

문제

 

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#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 n;
	cin >> n;
	
	string a;
	string b;
	string result;

	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;
}

1. 

먼저 해당 코드를 사용할 때 그냥 ing 나 long long으로 접근을 하려 하면 오류가 발생합니다. 왜냐하면 n 이 100으로 지정되어 있기 때문에 이는 overflow가 발생하기 때문인데요.

 

이렇게 오버플로우가 발생할 경우 c++에서는 다른 방식으로 사용해줘야 하는데요. 바로 string 문자열을 통해 해결해주는 것이 그 방식입니다. 

 

따라서 숫자를 string으로 받아서 sum을 구해주는 함수를 써주어쓴ㄴ데요.

 

sum 함수 구성 설명

1.변수 초기화
num: 각 자릿수의 합을 저장할 임시 변수.
carry: 자릿수 합산 시 발생하는 올림수(carry-over).
result: 최종 결과를 저장할 문자열.

 

2.문자열 뒤집기:
숫자의 가장 낮은 자릿수(일의 자리)부터 덧셈을 시작하기 위해 두 입력 문자열 x와 y를 뒤집습니다.

 

3.문자열 길이 조정:
두 문자열의 길이가 다를 경우, 짧은 문자열의 뒤(원래의 시작 부분)에 '0'을 추가하여 길이를 맞춥니다. 이렇게 함으로써 각 자릿수를 정확히 맞출 수 있습니다.

 

4.자릿수 별 덧셈:
문자열의 각 자릿수를 순회하면서 덧셈을 수행합니다. x[i] - '0'과 y[i] - '0'은 문자를 해당하는 숫자로 변환합니다.
이들을 더하고 이전 자리에서의 올림수 carry를 더한 후, 10으로 나눈 나머지를 결과 문자열에 추가합니다 (이는 현재 자릿수의 값). 올림수는 덧셈 결과를 10으로 나눈 몫으로 계산됩니다.

 

5.마지막 올림수 처리:
모든 자릿수의 덧셈이 끝난 후, 남아 있는 carry가 있다면 결과 문자열에 추가합니다.

 

6.결과 문자열 뒤집기:
덧셈을 뒤집어서 진행했기 때문에, 최종 결과도 뒤집어 원래 순서대로 조정합니다.

 

 

이런식으로 만들어 준 것입니다. 파이썬을 쓰면 오버플로우가 발생하지 않아서 간단하지만 c++의 경우 오버플로우가 발생하여 이런 식으로 해주어야 하는 번거로움이 존재합니다.