[Bronze V] <15740> "A+B - 9"

[Bronze V]  <15740> "A+B - 9" 문제 링크: https://www.acmicpc.net/problem/15740

15740번: A+B - 9

 

 

문제는 기초부터 풀고 있었는데

carry에 대한 문제가 나오더군요!

자료형이 담지 못하는 수는 어떻게 계산할까요?

 

언어에서 제공하는 operator가 아닌, 직접 계산기를 만드는 겁니다!

 

성인이 된다면 기초적인 산수는 암산으로도 가능합니다!

하지만 산수를 배울 때 기본적으로 우리는 초등학교 때 배웠던 올림수(carry)를 사용했었죠!

 

"13 + 9" 를 계산할 때 저희는 3 + 9를 먼저 하고 12가 나오니 12중 10은 10에자리에 더해주고 나머지를 적었죠!

그래서 22가 나옵니다.

 

 

 

실제로 논리회로를 짤 때에는 이런 식으로 회로를 구성한답니다!

 

그리고 해당 문제에서는 거의 무한한 수를 더하기 위한 알고리즘을 만들라고 했습니다!

무한한 수를 자료형에 담을 수 있는 적합한 방법은 문자열 입니다!

 

저는 A와 B를 문자열로 받고, 자리마다 하나씩 하나씩 더하고 올림수가 있다면

다음 자리에 1을 더해주고, 그렇게 계산한 값들을 결과 문자열에 저장하는 코드를 짰습니다!

 

일단 제 알고리즘은 먼저 편의를 위해 만들어야하는 함수가 있습니다!

 

   1. 음수인지 판별하는 함수인 IsNumNegative()

   2. 문자열을 반전시켜주는 함수인 ReverseStr()

   3. 자릿수를 맞추기 위해 빈 자리수를 0으로 필터링해주는 함수인 filltering()

 

위 함수들을 먼저 만들었습니다.

< 함수 코드 >

bool IsNumNegative ( string &str )
{
    if ( str.front() == '-' )
    {
        return true;
    }
    else 
    {
        return false;
    }
}


string ReverseStr ( string str )
{
    string revstr = "";

    for ( int i = str.length() - 1; i >= 0; i-- )
    {
        revstr += str[i];
    }

    return revstr;
}


string filltering ( string str, int Maxlen )
{
    str = ReverseStr(str);
    str.resize(Maxlen,'0');
    return str;
}

 

일단 메인 함수부터 보겠습니다.

 

< 메인 함수 코드 >

int main()
{
    string A;
    string B;
    string res = "";

    cin >> A >> B;

    bool Is_A_Nega = IsNumNegative(A);
    bool Is_B_Nega = IsNumNegative(B);

    if ( Is_A_Nega && Is_B_Nega )
    {
        A.erase(0, 1);
        B.erase(0, 1);

        if ( A.length() >= B.length() )
        {
            res = '-' + add(A, B);
        }
        else
        {
            res = '-' + add(B, A);
        }
    }
    else if ( Is_A_Nega == true )
    {
        A.erase(0, 1);

        if ( A.length() > B.length() )
        {
            res = "-" + sub(A, B);
        }
        else if ( B.length() > A.length() )
        {
            res = sub(B, A);
        }
        else
        {
            if ( A > B )
            {
                res = "-" + sub(A, B);
            }
            else if ( A < B )
            {
                res = sub(B, A);
            }
            else
            {
                res = "0";
            }
        }
    }
    else if ( Is_B_Nega == true )
    {
        B.erase(0, 1);

        if ( B.length() > A.length() )
        {
            res = "-" + sub(B, A);
        }
        else if ( B.length() < A.length() )
        {
            res = sub(A, B);
        }
        else
        {
            if ( B > A )
            {
                res = "-" + sub(B, A);
            }
            else if ( B < A )
            {
                res = sub(A, B);
            }
            else
            {
                res = "0";
            }
        }
    }
    else
    {
        if ( A.length() >= B.length() )
        {
            res = add(A, B);
        }
        else
        {
            res = add(B, A);
        }
    }

    cout << res << endl;
}

 

제가 생각한 경우는 4가지 입니다.

 

   1. 둘 다 음수인 경우

   2. 하나만 음수인데, 음수가 큰 경우

   3. 하나만 음수인데, 음수가 작은 경우

   4. 둘 다 양수인 경우

 

 

if문과 Is_A_Nega, Is_B_Nega 를 이용하여 위 경우를 구분지어 계산을 해주었습니다.

 

일단 서로 양수이거나 서로 음수인 경우는 단순히 더해주면 됩니다. 마지막에 ' - '를 붙여주면 그만입니다.

 

그런데 하나만 음수라면 말이 달라집니다.더하기가 아니라 뺄셈을 해주어야 하기 때문이죠.

 

뺄셈을 할 때 중요한 것은큰수와 작은수를 구분해야 한다고 생각했습니다.

 

 

왜냐하면 보통 큰수에서 작은수를 빼기 때문입니다.만약 문제가 작은수에서 큰수를 빼는 문제여도 보통 뒤집어서 큰수에서 작은 수를 빼고 마이너스를 붙여주기 때문이죠.

 

그래서 큰 수를 무조건 A로 두게끔 만들고 A를 기준으로 자리수를 맞춰주었습니다.

자리수를 맞추는것은 더하기도 동일합니다. 더하기도 보통 큰수에서 작은수를 더하기 때문이죠.

 

---

여기서 중요한건 string인데 어떻게 대소비교를 하지??

---

라는 의문이 생길 겁니다. 

하지만 가능합니다. 해당 연산자가 있기 때문이죠

 

    string A = "100"

    string B = "110"

 

논리연산자인 '<, >, <=, >=' 가 string에선 다른 작용을 합니다!

이게 바로 객체지향에서 배우는 다형성입니다.

string은 연산이 좀 신기하게 됩니다.

배열의 자리수끼리 비교를 합니다.

---

   

A[0] = 1

B[0] = 1

 

둘 다 1 이므로 해당 자리수는 같습니다.

 

A[1] = 0

B[1] = 1

 

이번엔 A[1]이 B[1] 보다 작습니다.

고로 B가 A보다 크다 라는 결과를 반환합니다.

 

A > B 라고 되어있었으면 "false"가 반환되겠죠?

---

하지만 여기서 주의해야할 점이 있습니다.

 

string A = "21"

string B = "100"

 

만약 위와 같이 수가 주어진다면 결과는 "A가 크다."라고 나옵니다.

 

이유는 자리수마다 비교를 하기 때문입니다.

 

---

그럼 어떻게 큰수를 비교한다는거지?

---

아주 간단합니다.

문자열의 길이를 먼저 봐주면 됩니다.

 

A.length()와 B.length() 의 대소비교를 먼저 해주고 만약 자리수가 같다면 그때 논리 연산자를 쓰는겁니다.

간단하죠?

 

결론적으로 메인함수에서는 음수 판별과 숫자의 크기를 비교하여 함수에 정확한 매개변수를 입력해줍니다.

큰 틀은 이렇습니다.

 

    1. 음수 판별을 한다.

    2. 대소 비교를 한다.

    3. 큰 수는 A에 집어넣는다.

    4. 계산할 때 string에 '-' 문자는 빼준다. (숫자의 크기에 따라 마이너스를 붙일지 말지를 구분)

    5. 수에 따라 add() 함수 혹은 sub() 함수를 호출하여 결과를 구한다.

    6. 출력한다.

 

 

아무튼 이렇게 해서 메인함수를 만들어주고 이제 더하기 함수와 빼기 함수를 만들어야겠죠?

 

   1. 더하는 함수 add()

   2. 빼는 함수 sub()

 

코드부터 보겠습니다.

 

< add( ) 함수 >

string add ( string A, string B )
{
    string res = "";
    int Maxlen = A.length();
    int carry = 0;

    A = ReverseStr(A);
    B = filltering(B, Maxlen);

    for ( int i = 0; i < Maxlen; i++ )
    {
        int i_A = (int)A[i] - 48;
        int i_B = (int)B[i] - 48;
        int i_res;

        if ( carry == 0 )
        {
            i_res = i_A + i_B;
        }
        else
        {
            i_res = i_A + i_B + carry;
            carry--;
        }
        
        if ( i_res >= 10 )
        {
            i_res -= 10;
            carry++;
        }

        res += to_string(i_res);
    }
    if ( carry == 1 )
    {
        res += "1";
    }

    res = ReverseStr(res);
    return res;
}

 

과정은 이렇습니다.

 

    1. add 함수에서 큰 수인 A를 기준으로 필터링을 합니다.

         예)  A = "30000", B = "25"   =>  A = "30000", B = "00025"

    2. 더해주기위해서 A, B를 전부 반전시켜준다. (B는 filltering에서 반전이 되어나옴)

    3. 

    4. string의 주소마다 있는 char 자료형의 데이터를 int로 변환하고 48을 빼준다(아스키코드 참고)

    5. 이후는 위 설명한 대로 자리마다 계산해준다.

    6. loop상의 문제로 연산이 끝나도 carry가 남아있다면 문자열 뒤에 1을 붙여준다.

    7. 그렇게 만들어진 결과 문자열을 다시 반전시켜주고 리턴한다.

 

< sub( ) 함수 >

string sub ( string A, string B )
{
    string res = "";
    int Maxlen = A.length();
    int carry = 0;

    A = ReverseStr(A);
    B = filltering(B, Maxlen);

    for ( int i = 0; i < Maxlen; i++ )
    {
        int i_A = (int)A[i] - 48;
        int i_B = (int)B[i] - 48;
        int i_res;

        if ( carry == 0 )
        {
            i_res = i_A - i_B;
        }
        else
        {
            i_res = i_A - i_B - carry;
            carry--;
        }

        if ( i_res < 0 )
        {
            i_res += 10;
            carry++;
        }

        res += to_string(i_res);
    }

    res = ReverseStr(res);

    while ( res[0] == '0' )
    {
        res.erase(0, 1);
    }

    return res;
}

 

위 add() 함수와 다른 점은 빼주는 것이고,  carry가 생기면 다음 연산에서 1을 빼주면 된다.

여기서 문제점이 있다. 바로 string의 문자열 상 마지막 연산이 0으로 끝날 수가 있다는 점이다.

 

    (계산 후 반전 전) "340"    ->    (반전 후) "043"

 

이때 답의 자료형이 숫자형이라면 0이 생략되었겠지만 string이기 때문에 사라지지 않는 오류가 발생했다.

하여 반전 이후 결과의 첫 문자가 0이 아닐 때 까지 앞 문자를 지워주는 작업을 해주고 리턴한다.

 

<결과>

A : 82360723895032679247690236092389048670880273896787695480682948679384

B : -982375979685498679836598248759854668934985

위 두 숫자를 입력하여 더해주었다.

결과 : 82360723895032679247690235110013068985381594060189446720828279744399

 

---

아니 이걸 어떻게 알지? 대충 맞는것 같은데 하나하나 내가 계산해야하나...

그래서 큰 수 계산해주는 웹사이트를 검색했더니 당연하게 있었다.

 

---

링크: https://www.numerics.info/

Numerics Calculator & Converter

---

 

나의코드 결과 : 82360723895032679247690235110013068985381594060189446720828279744399

웹사이트 결과 : 82360723895032679247690235110013068985381594060189446720828279744399

 

---

 

정확하군. 후후

이제 백준에 내볼까?

 

 

 

 

 

내 인생 목표를 향해!

 

다들 공부 화이팅 하세요!

읽어주셔서 감사합니다!