이번에는 백준 15353번 큰 수 A+B 문제를 풀어보았습니다.
문제를 처음 봤을 때 입력되는 수의 크기가 매우 크기 때문에 일반적인 정수형으로는 저장할 수 없다는 점을 확인했습니다.
그래서 문자열로 입력받은 뒤, 직접 큰 수의 덧셈을 구현하는 방식으로 해결하였습니다.
일의 자리부터 차례대로 더하면서 자리올림을 함께 관리하도록 구현하였습니다.
문제 설명
두 정수 A와 B가 주어집니다.
하지만 두 수의 크기가 매우 크기 때문에 일반적인 정수형 자료형으로는 저장할 수 없습니다.
두 수의 합을 출력하는 문제입니다.
풀이 아이디어
두 수를 문자열로 입력받았습니다.
자리수가 더 작은 수를 기준으로 일의 자리부터 같은 자리끼리 더하였습니다.
각 자리에서 합이 10 이상이 되는 경우에는 자리올림을 저장하였습니다.
이후 자리수가 더 큰 수의 남은 자리도 계속 계산하였습니다.
마지막 계산이 끝난 뒤에도 자리올림이 남아있다면 가장 앞자리에 추가하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string A, B, ret;
cin >> A >> B;
int carr = 0;
bool A_large;
int cnt, aidx = A.size()-1, bidx = B.size()-1;
if (A.size() > B.size()) {
A_large = true;
cnt = B.size();
} else {
A_large = false;
cnt = A.size();
}
while(cnt--) {
int a, b;
a = A[aidx--] - '0';
b = B[bidx--] - '0';
if (a+b+carr >= 10) {
ret = to_string((a + b + carr - 10)) + ret;
carr = 1;
} else {
ret = to_string(a + b + carr) + ret;
carr = 0;
}
}
if (A_large) {
while(true){
if (aidx == -1) break;
int a = A[aidx--] - '0';
if (a+carr >= 10) {
ret = to_string((a + carr - 10)) + ret;
carr = 1;
} else {
ret = to_string(a + carr) + ret;
carr = 0;
}
}
} else {
while(true){
if (bidx == -1) break;
int b = B[bidx--] - '0';
if (b+carr >= 10) {
ret = to_string((b + carr - 10)) + ret;
carr = 1;
} else {
ret = to_string(b + carr) + ret;
carr = 0;
}
}
}
if (carr) {
ret = to_string(carr) + ret;
}
cout << ret << '\n';
return 0;
}풀이 흐름
- 두 수를 문자열로 입력받습니다.
- 자리수가 더 작은 수부터 같은 자리끼리 더합니다.
- 각 자리의 자리올림을 계산합니다.
- 자리수가 더 큰 수의 남은 자리도 계속 계산합니다.
- 마지막 자리올림이 남아있는지 확인합니다.
- 결과를 출력합니다.
구현 포인트
1. 문자열로 입력받기
입력되는 수의 크기가 매우 크기 때문에 문자열로 입력받았습니다.
string A, B, ret;이후 각 문자를 숫자로 변환하여 계산하였습니다.
2. 같은 자리끼리 덧셈
일의 자리부터 같은 자리끼리 계산하였습니다.
int a = A[aidx--] - '0';
int b = B[bidx--] - '0';현재 자리의 두 숫자와 자리올림을 함께 더하였습니다.
3. 자리올림 처리
현재 자리의 합이 10 이상이라면 자리올림을 발생시켰습니다.
if (a + b + carr >= 10) {
ret = to_string(a + b + carr - 10) + ret;
carr = 1;
}그렇지 않은 경우에는 그대로 결과를 저장하였습니다.
else {
ret = to_string(a + b + carr) + ret;
carr = 0;
}4. 자리수가 다른 경우 처리
자리수가 더 큰 수는 아직 계산하지 않은 숫자가 남아있습니다.
남은 자리도 계속 자리올림과 함께 계산하였습니다.
if (A_large) {
...
}
else {
...
}남은 숫자들을 끝까지 처리하도록 구현하였습니다.
5. 마지막 자리올림 처리
모든 계산이 끝난 뒤에도 자리올림이 남아있을 수 있습니다.
예를 들어
999
+ 1
----
1000과 같은 경우입니다.
이를 위해 마지막에 한 번 더 확인하였습니다.
if (carr) {
ret = to_string(carr) + ret;
}가장 앞자리에 자리올림을 추가하여 최종 결과를 완성하였습니다.
