C++에서 큰 수를 11로 나눈 나머지 구하기: 자릿수별 계산 방법

이 문제에서는 매우 큰 수가 문자열 num 형태로 주어집니다. 우리의 과제는 C++을 사용하여 이 큰 수를 11로 나눴을 때의 나머지를 구하는 프로그램을 작성하는 것입니다.

문제 설명

문자열로 표현된 수를 11로 나눈 나머지를 구해야 합니다. 수가 너무 커서 일반적인 정수 자료형에 담을 수 없기 때문에, 문자열 그대로 처리해야 합니다.

예제로 문제 이해하기

입력

num = "43212981843718452"

출력

해결 접근 방법

나머지를 구하려면 당연히 나눗셈을 해야 합니다. 하지만 아주 큰 수를 한 번에 나누는 것은 복잡한 작업이므로, 프로세스를 단순화하기 위해 자릿수별로 하나씩 나누는 방식을 사용합니다.

구체적인 동작 원리는 다음과 같습니다.

최상위 자릿수(MSB)부터 최하위 자릿수(LSB)까지 문자열을 순회합니다.
각 단계에서 이전 단계의 나머지에 10을 곱한 뒤 현재 자릿수를 더합니다.
그 값을 11로 나눈 나머지를 다시 저장합니다.
이 과정을 문자열 전체에 대해 반복하면, 최종적으로 남는 값이 전체 수를 11로 나눈 나머지와 같습니다.

이 방법은 모듈러 연산의 성질인 (a * 10 + b) % m = ((a % m) * 10 + b) % m을 활용한 것으로, 오버플로우 없이 어떤 크기의 수든 처리할 수 있다는 장점이 있습니다.

솔루션 구현 예시

예제 코드

#include <iostream>
#include <string.h>
using namespace std;
int calcRem(string num){
    int currDigit, rem = 0;
    for (int i = 0; i < num.length(); i++) {
        currDigit = rem * 10 + (num[i] - '0');
        rem = currDigit % 11;
    }
    return rem;
}
int main() {
    string num = "43212981843718452";
    cout<<"큰 수를 11로 나눈 나머지: "<<calcRem(num);
    return 0;
}

출력 결과

큰 수를 11로 나눈 나머지: 7

코드 설명

calcRem 함수는 문자열의 각 문자를 왼쪽부터 순회하며 누적 나머지 rem을 갱신합니다. num[i] - '0'은 문자 형태의 숫자를 실제 정숫값으로 변환하는 부분입니다. 시간 복잡도는 문자열 길이에 비례하는 O(n)으로 매우 효율적입니다.

이 방식은 11뿐만 아니라 임의의 제수에 대해서도 동일하게 응용할 수 있으므로, 큰 수의 모듈러 연산이 필요한 다양한 문제(예: 소수 판정, 해싱 등)에 유용하게 활용됩니다.