[백준] 10757번 : 큰 수 A+B

문제

 

---

풀이

 

입력으로 들어오는 값의 범위가 커서 단순한 덧셈 연산으로는 해결할 수 없다.

구몬 수학을 풀던 초등학교 시절로 기억을 되돌려보면

 

이런식으로 1의 자리부터 더하는게 좋을 것이다. 그런데 위와 같이 두 수의 자릿수가 다르면 어떻게 될까..?

여러 방법이 있겠지만 가장 간단한 방법은

 

이렇게 0을 붙여주는 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
	string str1, str2;
	vector<int> A, B, C;
	bool isCarry = false; //받아올림 여부

	cin >> str1 >> str2;
	if (str1.size() < str2.size()) //str1(A)의 길이가 더 길도록
		swap(str1, str2);

	int dist = str1.size() - str2.size();
	for (int i = 0; i < str1.size(); i++) {
		A.push_back(str1[i] - '0');
		if (i < dist)
			B.push_back(0);
		else
			B.push_back(str2[i - dist] - '0');
	}

	for (int i = str1.size() - 1; i >= 0; i--) {
		int temp;
		if (isCarry) //받아올림이 있었나?
			temp = A[i] + B[i] + 1;
		else
			temp = A[i] + B[i];

		if (temp >= 10) {
			isCarry = true;
			temp -= 10;
		}
		else
			isCarry = false;

		C.push_back(temp);
	}
	if (isCarry) //마지막에 받아올림이 있었을지도 모르니까
		C.push_back(1);
	for (int i = C.size() - 1; i >= 0; i--)
		cout << C[i];
}

이번 글부터는 코드를 분리해서 설명하기로 했다.

 

	cin >> str1 >> str2;
	if (str1.size() < str2.size()) //str1(A)의 길이가 더 길도록
		swap(str1, str2);

길이가 워낙 길기때문에 일단 string으로 입력을 받는다.

그리고 두 string의 길이를 비교해 str1이 더 긴 문자열이 되도록 swap한다.

 

	int dist = str1.size() - str2.size();
	for (int i = 0; i < str1.size(); i++) {
		A.push_back(str1[i] - '0');
		if (i < dist)
			B.push_back(0);
		else
			B.push_back(str2[i - dist] - '0');
	}

vector로 선언한 int배열 A, B에 str1과 str2의 값을 입력한다.

str1은 그냥 입력해도 괜찮지만, str2는 str1과의 길이 차이만큼 앞에 0을 삽입해야한다.

 

	for (int i = str1.size() - 1; i >= 0; i--) {
		int temp;
		if (isCarry) //받아올림이 있었나?
			temp = A[i] + B[i] + 1;
		else
			temp = A[i] + B[i];

		if (temp >= 10) {
			isCarry = true;
			temp -= 10;
		}
		else
			isCarry = false;

		C.push_back(temp);
	}

1의 자리부터 더해야 하니 배열의 가장 마지막 수부터 조회를 하며 더해나간다.

이전 자리에서 받아올림이 있었는지 체크하고 이번 덧셈으로 받아올림이 생겼는지도 체크한다.

 

	if (isCarry) //마지막에 받아올림이 있었을지도 모르니까
		C.push_back(1);

99+99의 경우라면 마지막에 받아올림이 하나 생긴다. 그걸 놓치지 않도록 체크한다.

 

	for (int i = C.size() - 1; i >= 0; i--)
		cout << C[i];

111+123의 경우라면 432와 같이 역순으로 저장됐을테니 뒤에서부터 출력한다.