long long, unsigned long long 으로도 못 담는 긴 숫자들이라 string 에 숫자들을 저장했다.
연산하려면 자리수마다 숫자를 더해줘야 하니까, string을 vector<int>로 모두 변환했다.
숫자 자리수가 다르더라도, 덧셈을 할 때는 두 숫자의 1의 자리 부터 하니까. 두 숫자의 길이가 맞아야 한다.
짧은 숫자 vector에 0을 먼저 넣어둬서 a_vec과 b_vec의 길이를 맞춘다.
vector의 맨 뒤가 1의 자리니까. 뒤에서부터 연산을 한다. 1의자리, 10의 자리, 100의 자리... 순이다.
연산 결과는 answer 문자열에 한 자리 숫자를 붙인다. (숫자에 ‘0’을 더하면 문자 ‘0’이 된다. )
답 출력 직전에 answer 문자열을 뒤집으면, 정상 숫자로 출력할 수 있다.
올림수 처리가 중요하다.
예를 들어, 7 + 5 = 12 가 되니까. 올림수가 발생한다.
carry 가 생기면, 1의 값을 갖게 했다. 그래서 다음 연산때 1을 더해주고, carry를 다시 0으로 돌려놓는다.
#include <bits/stdc++.h>
using namespace std;
string a, b, answer;
vector<int> a_vec, b_vec;
int carry, temp_sum; // 올림수, 한 자리수 더함.
// 숫자 + '0' == 문자
// 문자 - '0' == 숫자
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a >> b;
if(a.size() < b.size()) swap(a, b);
int diff_len = a.size() - b.size();
// a, b 문자열의 문자를 하나씩 int 벡터로 넣는다.
for(int i = 0; i < a.size() ; i++) a_vec.push_back(a[i]-'0');
for(int i = 0; i < diff_len; i++) b_vec.push_back(0);
for(int i = 0; i < b.size(); i++) b_vec.push_back(b[i]-'0');
for(int i = a_vec.size()-1; i >= 0 ; i--){ // 뒤 부터 앞으로
temp_sum = a_vec[i] + b_vec[i];
if(carry == 1){ // 이전에 올림수가 있었다면, 1 더한다.
temp_sum++;
carry = 0;
}
if(temp_sum > 9){
temp_sum %= 10;
carry = 1; // 올림수 발생했으니까 1로 변경.
}
answer += (temp_sum + '0'); // 숫자를 문자열에 이어붙인다
}
if(carry == 1) answer += '1'; // 올림수가 있다면, 1을 덧붙임
reverse(answer.begin(), answer.end()); // 문자를 뒤집기
cout << answer;
return 0;
}
참고
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 시리얼 번호 백준 1431번 c++ (0) | 2022.02.10 |
|---|---|
| 곱셈 백준 1629번 c++ (0) | 2022.02.09 |
| 피보나치 수 4 백준 10826번 c++ (0) | 2022.02.08 |
| 피보나치 수 5 백준 10870번 c++ (0) | 2022.02.08 |
| 피보나치 수 백준 2747번 c++ (0) | 2022.02.08 |