[C++] 백준(BOJ) - 15353 : 큰 수 A+B(2)

18 Dec 2023 in Develop on C++, Algorithm Last modified at: 2024-02-01

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 15353 : 큰 수 A+B(2)(링크)

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A,B < $10^{10000}$)

출력

첫째 줄에 A+B를 출력한다.

알고리즘

1. 문자열

풀이

1. long long 형의 공간 복잡도는 20억, 제시된 문제의 크기 제한은 10의 10000승 이므로 시간 초과 -> string 형으로 선회
2. 모든 연산은 끝에서 부터 진행된다는 기본 개념으로 접근
3. 두 정수 중 하나라도 남은 자리 수가 있다면 연산을 계속 진행하고, 더해서 10 이상의 수가 나오면 나머지 연산을 통해 1을 다음 자리수에 올려준다
4. reverse 함수를 통해 정답 도출

코드

// BOJ-15353 : 큰 수 A+B (2)
#include<bits/stdc++.h>
using namespace std;

string sum(string a, string b)
{
	int sum = 0;
	string res;
	while (a.size() || b.size() || sum)
	{
		if (a.size())
		{
			sum += a.back() - '0';
			a.pop_back();
		}
		if (b.size())
		{
			sum += b.back() - '0';
			b.pop_back();
		}
		res += sum % 10 + '0';
		sum /= 10; // 올림
	}
	reverse(res.begin(), res.end());
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string a, b;
	cin >> a >> b;
	cout << sum(a, b) << '\n';

	return 0;
}

평가

• 시간 복잡도를 고려하여 string을 이용하여 연산을 진행
• 문자열을 자유자재로 숫자로 변환하는 능력을 배양