(C++) - 백준(BOJ) 4388번 : 받아올림 답

www.acmicpc.net/problem/4388

4388번: 받아올림

문자열을 적절히 처리하는 문제였습니다.

 

 

풀이방법

 가장 긴 자리 수를 기준으로 일의자리부터 왼쪽으로 거슬러 올라가는 식으로 더해보고 비교해줍니다.

 이 때 짧은 자리를 가진 수가 overflow가 나면 안됩니다.

 1. 현재 자리 수가 짧은 자리 수에게도 있는 경우

    a의 현재 자리 수 + b의 현재 자리 + 받아올림 여부(cnt) >= 10이라면 carry++, cnt = 1;

    else cnt = 0으로 초기화

 2. 아닌 경우

    a의 현재 자리 수 + 받아올림 여부(cnt) >= 10이라면 carry++, cnt=1;

    else cnt = 0으로 초기화

Code

#include <bits/stdc++.h>
using namespace std;
string a, b;
int main(){
    while(1){
        int carry = 0;
        int cnt = 0;
        vector <string> num(2);
        cin >> num[0] >> num[1];
        if(num[0]=="0" && num[1]=="0") break;
        sort(num.rbegin(),num.rend());
        string a = num[0];
        string b = num[1];
        for(int i = 0; i < num[0].size(); i++){
            if(b[b.size()-1-i] -'0' >= 0){
                if(a[a.size()-1-i] -'0' + b[b.size()-1-i] -'0' + cnt >= 10){
                    carry++;
                    cnt = 1;
                }
                else cnt = 0;
            }
            else{
                if(a[a.size()-1-i] -'0' + cnt >= 10){
                    carry++;
                    cnt = 1;
                }
                else cnt = 0;
            }
        }
        cout << carry << '\n';
    }
}

Test Case 

 반례가 될 수 있는 테스트 케이스를 추가해보았습니다.

 

input

1 999

답

3

 

 

input

999 1

답

3