[알고리즘] 백준 15353 큰수 // 문자열, 덧셈

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

* 요약

• long long을 벗어난 덧셈은 문자열로 받아서 뒤 한자리씩 더하라, carry 처리 철저히.
• 숫자를 문자로 바꾸려면 + '0' 하면됨. // 1 + '0' == '1'
• string에도 pop back 쓸수있음

 

* 풀이1

이 코드의 알고리즘을 단계별로 요약하면:

1. 자릿수 맞추기 (Leading Zero)
   • 두 수의 길이를 비교
   • 짧은 수의 앞에 0을 붙여서 길이를 같게 만듦
   • 예: "123"과 "45" → "123"과 "045"
2. 덧셈 수행 (Right to Left)
   • 오른쪽(일의 자리)부터 왼쪽으로 진행
   • 각 자리에서:
     1. 같은 자리의 두 숫자를 더함
     2. 이전 자리에서 올림(carry)이 있으면 1 더함
     3. 합이 10 이상이면 carry=1로 설정
     4. 현재 자리의 값(sum%10)을 벡터에 저장
3. 마지막 처리
   • 마지막까지 carry가 있으면 가장 앞에 1 추가
   • 벡터를 뒤집어서 올바른 순서로 만듦
4. 결과 출력
   • 벡터의 모든 숫자를 순서대로 출력

예시 (123 + 45):

1. 자릿수 맞추기: "123" + "045"

2. 덧셈 수행:
   3 + 5 = 8  (carry=0) → v=[8]
   2 + 4 = 6  (carry=0) → v=[8,6]
   1 + 0 = 1  (carry=0) → v=[8,6,1]

3. 벡터 뒤집기: v=[1,6,8]

4. 결과: 168

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string a,b;

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


   cin>>a>>b;
   // 자릿수 맞춰야함 0으로
   if(a.size()>b.size()) {
      while(a.size()!=b.size()) {
         b="0"+b;
      }
   }
   else {
      while(a.size()!=b.size()) {
         a="0"+a;
      }
   }
   // cout<<a<<" "<<b<<"\n";

   // 뒤에서부터 한자리씩 더하기, 캐리넘기기
   vector<int> v; //계산결과 저장, 나중에 뒤집으면됨
   int n=a.size();
   int carry=0;
   for(int i=n-1;i>=0;--i) {
      int sum=(a[i]-'0') + (b[i]-'0');
      if(carry) sum+=1;
      if(sum >=10) {
         v.push_back(sum%10);
         carry=1;
      }
      else {
         v.push_back(sum);
         carry=0;
      }
   }
   // 마지막캐리가있는경우
   if(carry) {
      v.push_back(1);
   }

   reverse(v.begin(), v.end());
   for(auto i : v) {
      cout<<i;
   }

   return 0;
}

 

* 풀이2

우아한 풀이(string_add를 사용한 방식)를 단계별로 요약

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(); 
    }
    ret += (sum % 10) + '0'; 
    sum /= 10; 
} 

알고리즘 요약:

1. 한 번의 While문으로 모든 처리
   • 조건: 두 수에 처리할 자릿수가 남아있거나 캐리가 있는 동안 계속
2. 자릿수 처리 (Right to Left)
   • 자릿수 맞추기가 필요없음
   • pop_back()으로 뒤에서부터 한 자리씩 가져와서 처리
   • 짧은 수는 자연스럽게 0으로 처리됨
3. 덧셈 처리
   • sum에 현재 자릿수들의 합과 캐리를 누적
   • sum % 10: 현재 자릿수의 값
   • sum / 10: 다음으로 넘어갈 캐리
4. 결과 생성
   • 결과 문자열을 뒤에서부터 만듦
   • 마지막에 한 번만 뒤집기

예시 (123 + 45):

1회차: 3 + 5 = 8    ret="8"
2회차: 2 + 4 = 6    ret="86"
3회차: 1 + 0 = 1    ret="861"
뒤집기: "168"

첫 번째 방식과 비교했을 때 장점:

• 코드가 더 간결함
• 자릿수 맞추기가 필요없음
• while 하나로 모든 로직 처리
• 문자열 직접 수정으로 메모리 효율적

#include<bits/stdc++.h>
using namespace std;   

// 두 큰 수를 문자열로 받아서 더하는 함수
string string_add(string a, string b) {
   int sum = 0;      // 각 자리의 합과 캐리를 저장할 변수
   string ret;       // 결과를 저장할 문자열
   
   // 두 수 중 하나라도 처리할 자릿수가 남아있거나, 캐리(sum)가 있으면 계속 진행
   while(a.size() || b.size() || sum){
       // a에 남은 자릿수가 있으면
       if(a.size()) {
           sum += a.back() - '0';    // 마지막 자리 숫자를 더함
           a.pop_back();             // 처리한 자릿수 제거
       }
       
       // b에 남은 자릿수가 있으면
       if(b.size()) {
           sum += b.back() - '0';    // 마지막 자리 숫자를 더함
           b.pop_back();             // 처리한 자릿수 제거
       }
       
       ret += (sum % 10) + '0';      // 현재 자리의 값을 문자로 변환하여 결과 문자열에 추가
       sum /= 10;                    // 캐리값을 다음 자리로 넘김
   } 
   
   reverse(ret.begin(), ret.end());  // 뒤에서부터 계산했으므로 뒤집어줌
   return ret;
} 

string a, b; 

int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);   
   
   cin >> a >> b;    // 두 큰 수를 문자열로 입력받음
   cout << string_add(a, b) << '\n';  // 두 수를 더한 결과 출력
   
   return 0; 
}