이 문제에서는 매우 큰 수를 담고 있는 문자열 num과 정수 R이 주어집니다. 우리의 목표는 이 큰 수를 R로 나눈 나머지를 구하는 C++ 프로그램을 작성하는 것입니다.
문제 설명
문자열 형태로 주어진 거대한 숫자를 두 자리 정수인 r로 나눈 나머지를 계산해야 합니다. 숫자가 너무 커서 일반적인 정수 자료형에 담을 수 없기 때문에, 문자열 그대로 처리해야 한다는 점이 핵심입니다.
예제로 문제 이해하기
입력
num = "123423450942121"
r = 54
출력
7
해결 접근 방법
나머지를 구하려면 당연히 나눗셈 연산이 필요합니다. 하지만 아주 큰 수를 한 번에 나누는 것은 복잡하고 비효율적입니다. 이를 해결하기 위해 자릿수별로 하나씩 나누는 방식을 사용합니다.
구체적인 동작 과정은 다음과 같습니다.
1. 가장 왼쪽 자릿수(최상위 자릿수, MSB)부터 시작합니다.
2. 이전 단계에서 얻은 나머지에 10을 곱하고, 현재 자릿수를 더합니다.
3. 이 값을 R로 나눈 나머지를 새로운 나머지로 저장합니다.
4. 문자열의 끝(최하위 자릿수, LSB)까지 위 과정을 반복합니다.
5. 마지막에 남은 나머지가 곧 전체 숫자를 R로 나눈 나머지입니다.
이 방법이 성립하는 이유는 나머지 연산의 성질 때문입니다. 어떤 수를 자릿수별로 확장할 때, 기존 나머지에 10을 곱하고 새 자릿수를 더한 값의 나머지는 전체 수의 나머지와 동일하게 유지됩니다.
C++ 구현 코드
#include <iostream>
#include <string.h>
using namespace std;
int calcRem(string num, int R){
int currDigit, rem = 0;
for (int i = 0; i < num.length(); i++) {
currDigit = rem * 10 + (num[i] - '0');
rem = currDigit % R;
}
return rem;
}
int main() {
string num = "123423450942121";
int R = 54;
cout<<"큰 수를 r로 나눈 나머지는 "<<calcRem(num, R);
return 0;
}
실행 결과
큰 수를 r로 나눈 나머지는 7
코드 설명
calcRem 함수는 문자열의 각 문자를 순회하면서 (num[i] - '0') 연산으로 문자형 숫자를 실제 정숫값으로 변환합니다. 변수 rem에는 누적된 나머지가 저장되며, 루프가 끝나면 최종 나머지를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)으로, n은 문자열의 길이입니다. 따라서 숫자가 아무리 커도 자릿수에 비례하는 선형 시간 안에 결과를 얻을 수 있다는 장점이 있습니다.