매우 큰 수가 문자열 형태로 주어져 있고(예: num), 또 다른 큰 수 m이 주어졌다고 가정해 봅시다. 이때 나누기 연산을 활용해 몫을 구하고, 모듈로 연산을 활용해 나머지를 계산해 출력하는 것이 이번 문제의 목표입니다.
출력 형식은 다음과 같습니다.
Remainder = xxx; Quotient = yyy
예를 들어 num = "14598499948265358486", m = 487이라면 나머지는 430, 몫은 29976385930729688이 됩니다.
예시
입력: num = "214755974562154868"
m = 17
출력: Remainder = 15
quotient = 12632704386009109
입력: num = "214"
m = 5
출력: Remainder = 4
Quotient = 42
문제 해결 접근 방식
- 먼저 mod 변수를 0으로 초기화합니다.
- 왼쪽 자릿수부터 차례대로 순회하면서 mod = (mod * 10 + digit) % m 공식을 적용해 나머지를 갱신합니다.
- 몫은 quo[i] = mod / m 공식으로 구합니다. 여기서 i는 몫에서 해당 자릿수의 위치를 뜻합니다.
알고리즘
시작
1단계 → long long 타입(ll) 선언
2단계 → void quotientremainder(string num, ll m) 함수 정의
vector<int> vec 선언
ll mod = 0 으로 설정
반복문: i = 0, i < num.size(), i++ 조건으로 실행
digit = num[i] - '0' 설정
mod = mod * 10 + digit 설정
quo = mod / m 설정
vec.push_back(quo) 호출
mod = mod % m 설정
반복문 종료
mod에 저장된 나머지 값 출력
zeroflag = 0 으로 설정
반복문: i = 0, i < vec.size(), i++ 조건으로 실행
만약 vec[i] == 0 && zeroflag == 0 이라면,
continue (건너뜀)
zeroflag = 1 로 설정
vec[i] 값 출력
반복문 종료
반환
3단계 → int main() 함수
num = "14598499948265358486" 선언 및 할당
ll m = 487 선언 및 할당
quotientremainder(num, m) 함수 호출
종료
C++ 코드 구현
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 큰 수의 모듈로(나머지)를 계산하는 함수
void quotientremainder(string num, ll m) {
// 큰 수의 나머지 계산 결과를 저장할 벡터
vector<int> vec;
ll mod = 0;
// 한 자릿수씩 단계적으로 나눗셈 수행
for (int i = 0; i < num.size(); i++) {
int digit = num[i] - '0';
// 현재 자릿수를 이어 붙여 모듈로 값 갱신
mod = mod * 10 + digit;
// 몫 갱신
int quo = mod / m;
vec.push_back(quo);
// 다음 반복을 위해 mod 갱신
mod = mod % m;
}
cout << "\nRemainder : " << mod << "\n";
cout << "Quotient : ";
// 앞쪽의 불필요한 0을 제거하기 위한 플래그
bool zeroflag = 0;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == 0 && zeroflag == 0)
continue;
zeroflag = 1;
cout << vec[i];
}
return;
}
// 메인 함수
int main() {
string num = "14598499948265358486";
ll m = 487;
quotientremainder(num, m);
return 0;
}
출력 결과
Remainder : 430 Quotient : 29976385930729688
동작 원리
long long 같은 기본 정수형은 대략 18~19자리 숫자까지만 표현할 수 있습니다. 따라서 그보다 큰 수는 문자열로 다루어야 합니다. 이 프로그램은 우리가 손으로 세로 나눗셈을 하는 과정을 그대로 코드로 옮긴 것입니다. 왼쪽 자릿수부터 한 자리씩 가져와, 지금까지 누적된 나머지에 10을 곱하고 새 자릿수를 더한 값에 m을 나눕니다. 이때 얻는 몫은 결과 몫의 해당 자릿수가 되고, 나머지는 다음 자릿수 계산으로 넘어갑니다. 이 과정을 마지막 자릿수까지 반복하면 전체 몫과 최종 나머지를 얻을 수 있습니다.
이 알고리즘의 시간 복잡도는 입력 문자열의 길이에 비례하는 O(n)이며, 몫의 각 자릿수를 벡터에 저장하므로 공간 복잡도 역시 O(n)입니다. 또한 출력 단계에서 앞자리의 불필요한 0을 건너뛰는 zeroflag 처리 덕분에 결과가 깔끔하게 표시됩니다.