[BOJ-10757][C++] 큰 수 A+B

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

9223372036854775807 9223372036854775808

 

예제 출력 1

18446744073709551615

 

알고리즘 분류

• 수학
• 구현
• 사칙연산
• 임의 정밀도 / 큰 수 연산

 

문제 출처

https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

 

---

 

문제 해결 방법

• 큰 수의 합(Big Sum) 알고리즘을 이용하여 문제를 해결하였다.

 

큰 수의 합(Big Sum) 알고리즘

• 2개의 큰 수를 문자열(string) 자료형의 변수로 입력받은 후, 두 문자열을 이용하여 큰 수의 합을 구하는 알고리즘이다.

			
			
			
		
string Solution(string a, string b) {
    // a : 긴 자리의 수, b : 짧은 자리의 수
    if (a.size() < b.size()) {
        swap(a, b);
    }
 
    for (int lenB = b.size() - 1, lenA = a.size() - 1; lenB >= 0; lenB--, lenA--) {
        a[lenA] += (b[lenB] - '0');
    }
 
    for (int lenA = a.size() - 1; lenA > 0; lenA--) {
        if (a[lenA] > '9') {
            int carry = a[lenA] - '0';
            a[lenA - 1] = ((a[lenA - 1] - '0') + carry / 10) + '0';    // 올림수 계산
            a[lenA] = (carry % 10) + '0';
        }
    }
 
    // 첫 번째 자리의 수가 10 이상이 될 경우
    if (a[0] > '9') {
        string k;
 
        k += a[0];
        a[0] = ((a[0] - '0') % 10) + '0';
        k[0] = ((k[0] - '0') / 10) + '0';
        a = k + a;
    }
 
    return a;
}

 

예제를 이용하여 알고리즘 원리 이해하기

• a = 92345와 b = 8888이 있다고 하자.

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8

 

• 우선, 두 수를 입력 받으면 더 긴 자리의 수는 배열 a에, 더 짧은 자리의 수는 배열 b에 넣어지도록 한다.

			
			
			
		
// a : 긴 자리의 수, b : 짧은 자리의 수
if (a.size() < b.size()) {
    swap(a, b);
}

 

• 길이가 더 짧은 배열 b의 마지막 인덱스(b[4])를 기준으로, 배열 a와 배열 b의 인덱스를 하나씩 감소시켜 나가면서(lenB--, lenA--) 배열 a와 배열 b의 각각의 자릿수를 더하는 과정을 반복해준다.

			
			
			
		
for (int lenB = b.size() - 1, lenA = a.size() - 1; lenB >= 0; lenB--, lenA--) {
    a[lenA] += (b[lenB] - '0');
}

• b[lenB] - '0'은 문자를 숫자로 변환시켜주는 것이다.

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	9	10	11	12	13

 

•  배열 a에는 10 이상의 수들이 들어있게 되고, 이것들을 처리해줘야 한다.

			
			
			
		
for (int lenA = a.size() - 1; lenA > 0; lenA--) {
    if (a[lenA] > '9') {
        int carry = a[lenA] - '0';
        a[lenA - 1] = ((a[lenA - 1] - '0') + carry / 10) + '0';    // 올림수 계산
        a[lenA] = (carry % 10) + '0';
    }
}

 

 단계 1

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	9	10	11	12 + 1	3

 

 단계 2

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	9	10	11 + 1	3	3

 

 단계 3

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	9	10 + 1	2	3	3

 

 단계 4

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	9 + 1	1	2	3	3

 

 최종

a	a[0]	a[1]	a[2]	a[3]	a[4]
	9	2	3	4	5
b		b[0]	b[1]	b[2]	b[3]
		8	8	8	8
결과	a[0]	a[1]	a[2]	a[3]	a[4]
	10	1	2	3	3

 

• a[0]에 10 이상인 수가 들어있으므로, 이 부분을 처리해줘야 한다.
• 새로운 문자열 k를 생성해준 후, a[0]의 값을 넣어준다.
• 그리고 a[0]의 값은 a[0]의 값(10)에서 % 10 연산을 해준 값(0)을, k[0]의 값은 k[0]의 값(10)에서 / 10 연산을 해준 값으로 갱신해준다.
• 그리고 문자열 k와 a를 합한 값을 문자열 a로 지정해준다.

			
			
			
		
// 첫 번째 자리의 수가 10 이상이 될 경우
if (a[0] > '9') {
    string k;
    
    k = a[0];
    a[0] = ((a[0] - '0') % 10) + '0';
    k[0] = ((k[0] - '0') / 10) + '0';
    a = k + a;
}

 

 최종

a	a[0]	a[1]	a[2]	a[3]	a[4]
	10	1	2	3	3
k	k[0]
	10
a (a + k)	a[0] (=K[0])	a[1]	a[2]	a[3]	a[4]	a[5]
	1	0	1	2	3	3

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
string A, B;
 
void Input() {
    cin >> A >> B;
}
 
string Solution(string a, string b) {
    // a : 긴 자리의 수, b : 짧은 자리의 수
    if (a.size() < b.size()) {
        swap(a, b);
    }
 
    for (int lenB = b.size() - 1, lenA = a.size() - 1; lenB >= 0; lenB--, lenA--) {
        a[lenA] += (b[lenB] - '0');
    }
 
    for (int lenA = a.size() - 1; lenA > 0; lenA--) {
        if (a[lenA] > '9') {
            int carry = a[lenA] - '0';
            a[lenA - 1] = ((a[lenA - 1] - '0') + carry / 10) + '0';    // 올림수 계산
            a[lenA] = (carry % 10) + '0';
        }
    }
 
    // 첫 번째 자리의 수가 10 이상이 될 경우
    if (a[0] > '9') {
        string k;
 
        k = a[0];
        a[0] = ((a[0] - '0') % 10) + '0';
        k[0] = ((k[0] - '0') / 10) + '0';
        a = k + a;
    }
 
    return a;
}
 
void Output() {
    cout << Solution(A, B) << '\n';
}
 
void Solve() {
    Input();
    Output();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    Solve();
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [1차원 배열]
• 브론즈V