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

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

10757번: 큰 수 A+B

코드

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

int main() {
	vector<short> vec_A;
	vector<short> vec_B;
	vector<short> answer;
	
	string A, B;
	
	cin >> A >> B;
	
	for(char & char_A : A){
		vec_A.push_back(char_A - '0');
	}
	
	for(char & char_B : B){
		vec_B.push_back(char_B - '0');
	}
	
	reverse(vec_A.begin(), vec_A.end());
	reverse(vec_B.begin(), vec_B.end());
	int size_A = vec_A.size() , size_B = vec_B.size();
	
	int leng = size_A > size_B ?  size_A : size_B;
	int temp;
	short isCarry = 0;
	
	for(int i=0; i<leng; i++){
		if(i+1 >= size_A) vec_A.push_back(0);
		if(i+1 >= size_B) vec_B.push_back(0);
		
		temp = isCarry + vec_A[i] + vec_B[i];
		if(temp > 9){
			isCarry = 1;
			answer.push_back(temp % 10);
		}
		else{
			isCarry = 0;
			answer.push_back(temp);
		}
	}
	
	if(isCarry) answer.push_back(isCarry);
	
	reverse(answer.begin(), answer.end());
	
	for(int i=0; i < answer.size(); i++){
		cout << answer[i];
	}

	return 0;
}

 

풀이

개인적으로 이게 브론즈 5밖에 안되나 싶은 문제였다.

물론, 풀이 자체는 단순하기는 한데 그 풀이를 하기 위해까지의 과정이 은근 길고 귀찮고...

 

어쨌든 주어지는 수의 크기가 정말 크다. 10의 10000승.

int 자료형이 2의 32승밖에 안되니, 당연히 오버플로우가 나서 계산이 안될텐데

그럼 어떻게 이 수들을 계산해주어야 할까?

 

배열을 사용해주자.

 

1. String 타입으로 A, B 값을 받는다.

string A, B;
	
	cin >> A >> B;

 

2. 배열을 사용하던, Vector 를 사용하던... 받은 A, B 값의 각 자리수를 하나씩 저장해준다.

여기서 받은 String 타입의 수에서, 각 자리수의 값은 Character 타입인데 '0' 을 빼주면 int형 으로 받을 수 있다.

for(char & char_A : A)
	{
		vec_A.push_back(char_A - '0');
	}
	
for(char & char_B : B)
    	{
		vec_B.push_back(char_B - '0');
	}

 

3. index 0부터 읽어나가면 그 수의 큰 자리수부터 읽어나가는 것이다. 그렇기 때문에 reverse를 활용해 뒤집어주자.

reverse(vec_A.begin(), vec_A.end());
reverse(vec_B.begin(), vec_B.end());

예시) 

주어진 수 A가 1234 이고 vec_A에 저장했다면

vec_A[0] = 1

vec_A[1] = 2

vec_A[2] = 3

vec_A[3] = 4

이렇게 저장되어있다. 

하지만 덧셈을 하기위해서는 낮은자리수부터 계산을 해야하므로 뒤집어주어야한다.

 

4. 뒤집어준 두 배열에서 낮은 자리수부터 덧셈 시작

for(int i=0; i<leng; i++){
		if(i+1 >= size_A) vec_A.push_back(0);
		if(i+1 >= size_B) vec_B.push_back(0);
		
		temp = isCarry + vec_A[i] + vec_B[i];
		if(temp > 9){
			isCarry = 1;
			answer.push_back(temp % 10);
		}
		else{
			isCarry = 0;
			answer.push_back(temp);
		}
	}

문제에서 두 수의 길이가 같다는 조건이 없었다.

따라서 덧셈도중에 한 쪽은 아직 수가 남았는데 한 쪽은 끝났을 수 있으므로

두 수의 길이를 비교해서 부족한 쪽은 각 자리에 0을 넣어서 길이만 맞춰주고 계산

올림수도 생각을 해야한다.

그렇게 해서 더해진 값을 또 다른 배열에 저장

 

5. 더해진 값이 저장된 배열을 출력한다.