본문 바로가기
코딩과 알고리즘

백준 문제풀이 - 큰 수 A+B

반응형

오랜만에 백준 코딩 문제 풀이를 해보았습니다.

백준 문제 풀이는 코딩 실력을 테스트하는 일종의 연습용 사이트인데요.
참여자도 많고 문제도 어마어마하게 많습니다.

국내 '천하 제일 코딩대회'라고 해도 과언이 아닐텐데요.
개발자들끼리 서로 코딩 문제를 풀어 랭킹을 뽐내기 때문입니다.

다만 전혀 코드 분석 없어 대충 복붙해 넣기만 하는게 가능한 단점도 있는데요.
다른 분의 코드를 참조는 하되 풀이방법만 익히고 스스로 풀어보는게 중요합니다.
그렇지 않으면 실력이 늘지 않지요.

그나저나 오랜만에 로그인해보니 헉!
순위권이 10.000위권 밖으로 밀려나 있는게 아니지 않습니까? 두둥!!

개발자 블로거의 자존심(?)이 걸린 문제라 가만 있을수 없어
부랴부랴 문제를 풀어 10.000위권 안으로 진입시켜 놓았습니다.

 

다른데 전혀 참조하지 않고 혼자 풀어 본 문제 해답 하나 공유드려 봅니다.

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

문제
두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 A와 B가 주어진다. (0 < A,B < 10의 10000승)

출력
첫째 줄에 A+B를 출력한다.

예제입력
9223372036854775807 9223372036854775808

예제출력
18446744073709551615


알고리즘 해설

개념 잡기입니다.
이 부분은 컴퓨터 언어를 모르시는 분을 위한 해설편이기도 합니다 :)

널리 사용되는 컴퓨터 언어 중 하나인 C++ 언어에서 숫자를 계산할수 있는 가장 큰 자릿수는
양의 정수만 따졌을 때, 0부터 18,446,744,073,709,551,615 으로 약 1,800경입니다.
꽤 큰 수를 계산할 수 있습니다.
물론 그보다 더 큰수도 계산 가능하나 정확도를 포기해야 해서 이 문제에는 사용할 수 없습니다.

이 문제는 무려 10.000개나 되는 자릿수의 숫자 2개를 한치의 오차도 없이 더해야 하는 덧셈 문제인데요.
컴퓨터가 기본 내장하는 덧셈 기능이런 수를 정확히 계산할 수 없습니다.

그렇다면 어떻게 이 문제를 해결할 수 있을까요?
그건 바로 덧셈을 하는 것처럼 덧셈을 하는 특별한 기능을 직접 코딩하는 것입니다.

이 문제를 사람이 푼다고 가정해 볼까요?
우선 3개의 숫자만 생각해볼 때.
368과 745라는 숫자가 주어졌다고 가정합시다.

3 6 8
7 4 5

결과는 1,113 입니다.
손으로 직접 계산할 때는 올림을 계산하기 제일 마지막 숫자인 8+5를 계산해줍니다.
결과는 13이기 때문에 
그리고 3을 적어주고, 1이 올라갔다고 어딘가 표시를 해줍니다.

  1  
    3

그리고 다음 6+4를 계산하면서 올림된 1을 더해 11이 됩니다.
역시 1이 올라갔다고 어딘가 표시해주고, 1을 적어 줍니다.

1    
  1 3

 

그 다음 3+7을 계산하면서 올림된 1을 더해 11이 됩니다.
역시 1이 올라간 자리를 적어주기 위해 사각형을 하나더 그린 다음, 1을 적어줍니다.
사실 코딩 풀이에서는 복잡도를 줄이기 위해 미리 1자리를 더 잡아줍니다.

1      
  1 1 3

이제 더 계산할 수치가 없으니 마지막 올림된 1을 그대로 적어 줍니다.

1 1 1 3


이걸 컴퓨터가 소화할 수 있도록 코딩을 해주는 건데요.
( 참고로, 더욱 효율적인 알고리즘이 있을 수 있습니다. 이 풀이는 가장  FM적인 방법입니다. )

코딩결과

 

위 내용을 코딩한 것은 아래와 같습니다.
코딩은 주석이 최고인 것 같아, 설명 대신 주석으로 대체합니다.
하나 하나 주석을 달았기 때문에 내용이 좀 깁니다.

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

int main()
{
    // 더할 숫자 2개를 문자열 변수로 정의
    // C++에서는 최대 자릿수를 하나 더 더해
    // 10,000자리인 경우 10,001로 정의해야 합니다.
    char a[10001]; 
    char b[10001]; 

    // 숫자 2개를 문자열로 입력받습니다.
    cin >> a >> b; 

    // 문자열의 마지막 위치 계산
    // 0부터 시작하므로 -1을 해주어야 합니다
    int a_last = strlen(a)-1;
    int b_last = strlen(b)-1;

    // 결과를 보관할 변수를 10,001자리로 정의합니다.
    // 이때는 10,002로 정의해야 합니다.
    char c[10002];

    // 계산을 보관할 위치를
    // 부족하지 않게 지정합니다.
    int c_last = a_last;
    if (b_last > a_last)c_last = b_last;
    c_last++;

    // 모두 빈칸으로 메꿔 버립니다.
    memset(c, ' ', c_last+1);
    c[c_last + 1] = '\0';

    // 한글자씩 읽어 보관할 임시변수
    char c1, c2;
    // 한 자리수의 덧셈 결과 보관
    int mini_sum = 0;
    // 올림이 일어났는지 결과 보관
    bool carry = false;

    // 양쪽 모든 숫자가 바닥날때까지 계산합니다.
    while(a_last >= 0 || b_last >= 0){
        // 2개의 숫자를 읽습니다.
        c1 = a[a_last];
        c2 = b[b_last];

        // 합산을 0으로 초기화,
        mini_sum = 0; 

        // A 숫자가 남아 있고 정상적인 숫자라면 합산에 더합니다
        if (a_last >= 0 && c1 >= '0' && c1 <= '9')mini_sum += c1 - '0';
        // B 숫자가 남아 있고 정상적인 숫자라면 합산에 더합니다
        if (b_last >= 0 && c2 >= '0' && c2 <= '9')mini_sum += c2 - '0';
        // 과거에 올림이 일어났었다면 1을 더해 줍니다.
        if (carry == true)mini_sum++;
        // 더한 숫자가 10보다 크면
        // 10을 빼주고, 올림이 발생했다고 표시합니다.
        if (mini_sum >= 10) {
            carry = true;
            mini_sum -= 10;
        }
        // 10보다 크지 않으면
        // 올림은 일어나지 않았다고 초기화합니다.
        else carry = false;
        // 결과값을 C변수의 현재 위치에 적고
        // 위치를 하나 앞으로 당깁니다.
        c[c_last--] = mini_sum + '0';
        // 올림이 일어났다면 1을 미리 적어 둡니다.
        if (carry == true) c[c_last] = '1';
        // A의 숫자가 남아 있는 경우 
        // 다음 계산을 위해 한칸 당깁니다.
        if (a_last >= 0)a_last--;
        // B의 숫자가 남아 있는 경우 
        // 다음 계산을 위해 한칸 당깁니다.
        if (b_last >= 0)b_last--;
    }
    // C의 숫자에서 올림이 일어나지 않았다면 
    // 앞의 빈 칸을 출력하지 않기 위해
    // 뒤로 한칸 후퇴합니다.
    if (c[c_last] == ' ')c_last++;
    // 현재 포지션을 기준으로 C 변수를 출력합니다.
    printf("%s", &c[c_last]);

    return 0;
}

이를 백준에 돌려보면 결과는 아래와 같이 무사 통과!


필요하신 분에게 도움이 되시길 바랍니다. 그러면 이만 :)

도움이 되셨다면 공감 한방, 댓글은 굿잡!
감사합니다~

 

반응형