[백준] 큰수 A+B

1 분 소요

업데이트:

문제



문제해결 과정

  • 그냥 입력받은 두 개의 정수 값을 더하는 간단한 문제이다.
  • 하지만, 입력받을 수 있는 범위가 매우 크다는 것이 문제다.
  • C++이나 Java에서 int는 약 21억 정도의 최대 범위를 갖기 때문에, int 자료형으로 입력값을 받아 이 문제를 해결한다면 오버플로우가 발생할 것이다. (long 타입도 마찬가지)

  • python3 같은 경우에는 아무리 큰 정수를 변수에 저장하더라도 오버플로우를 발생시키지 않기 때문에 다음과 같은 코드로 간단하게 이 문제를 해결할 수 있다.

    A, B = map(int, input().split())
  
print(A+B)
  • 또는, Java에서도 큰수를 저장할 수 있는 BigInteger와 같은 타입을 제공한다.
  • 하지만, 이러한 언어적 장점을 활용하여 문제를 해결할 수도 있겠지만, 이러한 방식으로 해결하는 것이 정말 이 문제의 의도라고 생각하지는 않는다.
  • 그렇다면, 굉장히 큰 수를 안전하게 저장하기 위해 사용할 수 있는 자료형으로는 어떤것이 있을까?

  • 다음과 같이 숫자를 자리수 하나하나 배열로 넣어서 계산하면 되지 않을까?

  • 그리고 또 하나 주의해야할 점은 문제에서 입력받는 두 정수의 자리수가 서로 다를 수 있다는 것이다.

  • 이럴때는, 두 정수 중 더 큰 자리수의 길이에 맞게 배열을 할당받아 작은 정수를 입력받고 남는 부분은 0으로 채워넣는 방식으로 저장하는 것이 계산하기에 편리할 것이다.

  • 덧셈을 수행할 때, 마지막 자리수(배열의 마지막요소)부터 거꾸로 계산 하면서, 올림수를 각 자릿수 덧셈을 수행할때마다 잘 계산하면 원하는 결과를 얻을 수 있을 것이다.



코드

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

string A,B;
int a,b,carry=0;
vector<char> ret;
int main() {
    
    cin>>A>>B;

    int a_size=A.size(),b_size=B.size();
    
    if (a_size>b_size) {
        int diff = a_size-b_size;
        while(diff--) B='0'+B;
    } else {
        int diff = b_size-a_size;
        while(diff--) A='0'+A;
    }
    int t_size=A.size();
    for (int i=t_size-1;i>=0;i--) {
        a=A[i]-'0';
        b=B[i]-'0';
        int val=(a+b+carry)%10;
        carry=(a+b+carry)/10;
        ret.push_back(val+48);
    }
    if (carry>0) ret.push_back(carry+48);
    for (int i=ret.size()-1;i>=0;i--) {
        cout<<ret[i];
    }
    printf("\n");
    return 0;
}



결과

댓글남기기

참고