11의 배수

gcoco·2023년 5월 7일

안녕하세요! 과제 마감기한을 지키지 못해 우울함이 가득한 GCOCO입니다! 😨😱😰

때는 5월 7일..... 과제 기한을 5월 10일 마감으로 착각한 GCOCO.
하지만 5문제중 상단의 2문제만이 5월 10일까지 제출이었고, 하단의 3문제는 5월 8일 0시까지 제출이었습니다.
이 사실을 5월 7일 오후 10시에 깨달은 GCOCO는 빠르게 코딩을 시작하였으나 실력 부족으로 결국
2문제는 제때 제출하였으나 한 문제는 어려워 마감기한을 10분 넘기고 제출하고 말았습니다......

그러나 알고계셨나요? 마감기한 10분을 넘기고 제출한다 하여도 단 1점도 주지 않는다는것을! 0점이야!

포항이 웃으면? 포항항~~~(❁´◡`❁)(●'◡'●)╰(°▽°)╯

네. 정신이 나갔습니다!

좋습니다! 지나간 일은 잊고 새롭게 나아가는것이 진정한 사나이입니다!
제출은 제때 하지 못하였지만, 풀었다는 것만으로도 훌륭한 것!
인생이란 끊임없이 주어진 문제들을 헤쳐나가는 것!
조금 빠르면 어떻고 조금 늦으면 어떠하리. 해결했다는 것에 자신을 가지십시오!

참고로 5월 8일 오늘은 어버이날이지요?
하지만 평일이기에 저녁에 모이기가 어려울것같아 7일 저녁 부모님께 맛있는 식사를 사드리는 것으로
해결하였습니다. 아직 가난한 대학생이기에 부족함이 많았지만 어서 효도하고 싶은 마음이 가득합니다!
부모님께 사랑한다고 오늘은 꼭 말씀드려야겠습니다.

본론, 시작하겠습니다!

이상한 나라의 앨리스”의 저자인 루이스 캐롤(Lewis Carroll)
어떤 자연수가 11 로 나누어 떨어지는 지를 검사하기 위한 방법으로 다음과 같은 알고리즘을 고안하였다

그 알고리즘은 다음과 같습니다.

주어진 자연수가 한 자리 이상의 수인 경우에는 다음과 같은 과정을 반복하여 새로운 수
를 만들며, 새로 만들어진 수가 한 자리 수가 될 때까지 반복한다.
주어진 숫자의 맨 마지막 자리수를 떼어 낸다.
마지막 자리수를 떼어 내어 한 자리가 짧아진 수에서 떼어낸 마지막 수를 뺀다.
최종적으로 남은 한 자리 수가 0이면 주어진 원래의 수는 11로 나누어 떨어지는 자연수이다.
그렇지 않으면, 주어진 자연수는 11의 배수가 아니다.

예를들어 숫자 '27384'이 주어졌을 때를 봅시다.

2738 - 4 = 2734
273 - 4 = 269
26 - 9 = 17
1 - 7 = -6

실제로 27384를 11로 나눠보면 나누어 떨어지지 않습니다. 흥미로운 알고리즘이지요?
알고리즘 자체는 쉬운것 같습니다. 하지만 이 문제의 문제라면... 바로 입력이
1~100자리의 자연수였습니다!
참고로 0으로 시작하는 입력은 없었습니다.

자. 고민이 됩니다.
MS에서 제공하는 데이터 형식 범위를 보겠습니다!

역시 long long형! 믿고 있었다구!
자리수를 세 봅시다. 엥 23자리?
unsigned는 24자리?

택도 없었습니다!

아하... 이 문제는 그럼,,,,,, string으로 처리해야겠구나!

#include <iostream>
#include <string>

using namespace std;
//11의 배수인지 판단
bool check(string s) {
    while (s.length() > 1) {
        char cut;//마지막 숫자
        cut = s.back();
        s.pop_back();//마지막 숫자 떼기
        bool check = true;
        bool carry = false;//캐리가 있는지 확인
        int i = s.length() - 1;
        //뺄셈 작업 업데이트
        while (check) {
            if (!carry && s[i] < cut) {
                s[i] = s[i] - cut + 10 + '0';
                carry = true;
            }
            else if (!carry) {
                s[i] = s[i] - cut + '0';
                check = false;
            }
            else {
                if (s[i] == '0') {
                    s[i] = '9';
                }
                else {
                    s[i]--;
                    check = false;
                }

            }
            i--;
        }

    }
	//캐롤 알고리즘에 의해 값 리턴
    if (s == "0")
        return true;
    return false;
}
//11로 나눠주기
string divide(string s) {
    string answer;
    string tmp;
    int idx = 0;
    while (s.length() > 1) {
        tmp.push_back(s[idx]);
        //11보다 작으면 자리수 확대
        if(stoi(tmp)/11==0){
            idx++;
        }
        else {
        	//나눗셈 작업
            answer += to_string(stoi(tmp) / 11);
            string str2 = to_string(stoi(tmp) % 11);
            s.replace(0, 2, str2);
            tmp.clear();
            idx = 0;
        }
    }
    return answer;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string s;
        cin >> s;
        if (check(s)) {
            cout << divide(s) << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
    return 0;
}

코드는 위와 같습니다! 처음엔 입력의 범위를 확인하지 않고 코드를 작성하였지만 굉장히 큰 자연수를 마주하고 나서야 string으로 연산을 처리하였습니다.

작성된 함수를 간단히 살펴보면~

check : 11의 배수인지 판단하는 함수입니다. 캐롤이 제시한 알고리즘대로 실행하였고 평소 두 수의 뺄셈을 하듯이 연산을 수행하였습니다. 핵심은 carry를 통해 윗자리에서 수를 끌어와야 하는지 판단한 것입니다!
divide : 11로 나눠주는 역할을 하는 함수입니다. 숫자를 나누는 것처럼 이를 코드로 표현하였습니다.
핵심은 replace 함수를 사용한 것이겠군요!

생각보다 시간이 걸린 문제였습니다.... 역시 쉽지 않습니다!

패배하고 무너지고 포기하고 싶어져도 천천히 나아가는것이 진정한 사나이!

힘내보겠습니다.

감사합니다 ^_^