백준 15740번 A+B - 9 (C++)

문제 링크입니다: www.acmicpc.net/problem/15740

15740번: A+B - 9

Java나 Python으로 풀면 가뿐히 풀 수 있는 문제이지만 여태까지 C++로 풀어왔기 때문에 C++로 푼 문제였습니다.

코드에도 자세한 주석을 달아놨지만 이 문제를 풀기 위해서는 문자열로 입력받은 숫자들을 더하고 뺄 수 있어야 합니다.

 

덧셈 알고리즘은 아래와 같습니다. (add 함수)

0. 두 개의 BigInteger A와 B가 있다고 가정하겠습니다.

1. A와 B의 덧셈 결과의 길이는 최소 A와 B 중 더 큰 숫자의 길이이기 때문에 결괏값을 정의해줄 result 문자열의 길이를 A와 B 중 더 큰 문자열의 길이로 정의하고 각 자리를 모두 0으로 초기화합니다.

2. 끝자리부터 더해나가는데 이전 자리의 덧셈 결과에 carry가 존재하는지 확인 후 carry까지 더해줍니다.

(carry를 모를 경우 다음 링크를 참고해주세요! en.wikipedia.org/wiki/Carry_(arithmetic))

3. 마지막 자리까지 계산했는데도 carry가 존재한다면 result 문자열 맨 앞에 1을 추가해줍니다.

(예를 들자면 999 + 1 = 1000과 같은 경우)

 

뺄셈 알고리즘은 조금 더 복잡합니다. (subtract 함수)

0. 마찬가지로 BigInteger A와 B가 있다고 가정하겠습니다.

그리고 해당 알고리즘은 부호와 상관없이 절댓값 기준 더 큰 수로부터 작을 수를 빼는 함수입니다.

1. isFormerBiggerThanLatter 함수를 통해 B가 A보다 절댓값 기준으로 더 큰 경우 A와 B 값을 swap 해줍니다.

2. A와 B 문자열을 뒤집어주고 더 큰 수로부터 작은 수를 빼는 함수이므로 result 문자열을 A로 초기화해줍니다.

3. 앞자리부터 뺄셈을 진행하는데(뒤집어줬으므로 실제로는 맨 뒷자리부터) 이전 자리의 뺄셈 결과에 carry가 존재하는지 확인 후 carry까지 빼줍니다.

4. 마지막 자리까지 계산했는데도 carry가 존재한다면 result 문자열 마지막 자리(뒤집어줬으므로 실제로는 맨 앞자리) 숫자를 1 빼줍니다.

5. result 문자열을 다시 뒤집어주고 최초로 0이 아닌 인덱스를 찾아줍니다.

6. 5번에서 최초로 0이 아닌 인덱스를 찾았다면 최초로 0이 아닌 자리부터의 숫자들을 반환해주고, 찾지 못했다면 "0"을 반환해줍니다.

(결과가 다음과 같은 경우가 있을 수 있으므로: "00000000", "0001000") 

 

전체 알고리즘은 아래와 같습니다.

1. A와 B가 둘 다 양수일 경우 단순히 A와 B를 더해줍니다.

 

2. A와 B가 모두 음수일 경우 절댓값 A와 절댓값 B를 더해주고 해당 결과의 음수 값을 출력해줍니다.

 

3. A는 양수인데 B는 음수인 경우 아래와 같은 조건을 확인해줘야 합니다.

* 절댓값 기준 A가 B보다 큰가?

* 연산 결과가 0인가

3.1 절댓값 기준 A가 B보다 크거나 연산 결과가 0인 경우 결괏값을 그대로 출력해줍니다.

3.2 그렇지 않은 경우 음수 처리를 한 뒤 결과를 출력해줍니다.

 

4. A는 음수인데 B는 양수인 경우도 마찬가지로 3번과 같은 조건을 확인해줘야 합니다.

4.1 절댓값 기준 A가 B보다 크거나 연산 결과가 0이 아닌 경우 음수 처리를 한 뒤 결과를 출력해줍니다.

4.2 그렇지 않은 경우 결괏값을 그대로 출력해줍니다.

 

 

	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	// bigInteger 덧셈 함수
	string add(string s1, string s2)
	{
	// 덧셈의 결과 길이는 최소 s1과 s2 중 더 큰 숫자의 길이
	string result(max(s1.size(), s2.size()), '0');
	bool carry = false;
	// 끝에부터 더해 나감
	for (int i = 0; i < result.size(); i++)
	{
	int temp = carry;
	carry = false;
	if (i < s1.size())
	{
	temp += s1[s1.size() - i - 1] - '0';
	}
	if (i < s2.size())
	{
	temp += s2[s2.size() - i - 1] - '0';
	}
	if (temp >= 10)
	{
	carry = true;
	temp -= 10;
	}
	result[result.size() - i - 1] = temp + '0';
	}
	// 마지막에도 캐리가 있다면 맨 앞에 1 추가
	if (carry)
	{
	result.insert(result.begin(), '1');
	}
	return result;
	}
	// s1이 s2보다 큰 지 여부를 판별하는 함수
	bool isFormerBiggerThanLatter(string s1, string s2)
	{
	if (s1.size() != s2.size())
	{
	return s1.size() > s2.size();
	}
	for (int i = 0; i < s1.length(); i++)
	{
	if (s1[i] == s2[i])
	{
	continue;
	}
	return s1[i] > s2[i];
	}
	return true;
	}
	// bigInteger 뺄셈 함수 (부호는 판별 X)
	string subtract(string s1, string s2)
	{
	// 절댓값 기준 s1과 s2 중 더 큰 수로부터 더 작은 수를 빼는 함수이므로
	if (isFormerBiggerThanLatter(s1, s2) == false)
	{
	swap(s1, s2);
	}
	// s1과 s2를 거꾸로 뒤집는다
	reverse(s1.begin(), s1.end());
	reverse(s2.begin(), s2.end());
	// 더 큰 수로부터 더 작은 수를 빼므로 add 함수와 달리 result를 s1으로 초기화
	string result = s1;
	int carry = 0;
	for (int i = 0; i < result.size(); i++)
	{
	int tempCarry = carry;
	carry = 0;
	// carry가 존재한다면 s1[i]로부터 1 뺌
	int temp = (s1[i] - '0') - tempCarry;
	// 음수가 된다면 carry가 존재한다고 표시 후 10을 더해줌
	if (temp < 0)
	{
	carry = 1;
	temp += 10;
	}
	if (i < s2.size())
	{
	temp -= (s2[i] - '0');
	if (temp < 0)
	{
	carry = 1;
	temp += 10;
	}
	}
	result[i] = temp + '0';
	}
	// carry가 있다면 마지막 자리 숫자 1 빼줌
	if (carry)
	{
	int lastDigit = result[result.size() - 1];
	lastDigit--;
	result[result.size() - 1] = lastDigit + '0';
	}
	// 다시 뒤집어준 뒤
	reverse(result.begin(), result.end());
	// 최초로 0이 아닌 인덱스를 찾는다
	int firstNonZeroIdx = result.size();
	for (int i = 0; i < result.size(); i++)
	{
	if (result[i] != '0')
	{
	firstNonZeroIdx = i;
	break;
	}
	}
	// 모든 자리가 0이라면 0을 반환
	if (firstNonZeroIdx == result.size())
	{
	return "0";
	}
	// 최초로 0이 아닌 자리부터의 숫자들을 반환
	return result.substr(firstNonZeroIdx);
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string A, B;
	cin >> A >> B;
	int APositive = A[0] != '-';
	int BPositive = B[0] != '-';
	if (APositive && BPositive)
	{
	// 둘 다 양수
	cout << add(A, B) << "\n";
	}
	else if (APositive == false && BPositive == false)
	{
	// 둘 다 음수
	cout << "-" << add(A.substr(1), B.substr(1)) << "\n";
	}
	else if (APositive && BPositive == false)
	{
	// A 양수, B 음수
	string tempResult = subtract(A, B.substr(1));
	// 절댓값 기준 A가 B보다 크거나 연산결과가 0이라면 결과는 양수
	if (isFormerBiggerThanLatter(A, B.substr(1)) || tempResult == "0")
	{
	cout << tempResult << "\n";
	}
	else
	{
	cout << "-" << tempResult << "\n";
	}
	}
	else if (APositive == false && BPositive)
	{
	// A 음수, B 양수
	string tempResult = subtract(A.substr(1), B);
	// 절댓값 기준 A가 B보다 크거나 연산결과가 0이 아니라면 결과는 음수
	if (isFormerBiggerThanLatter(A.substr(1), B) && tempResult != "0")
	{
	cout << "-" << tempResult << "\n";
	}
	else
	{
	cout << tempResult << "\n";
	}
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~