이 글에서는 숫자 A에 N개의 자릿수를 추가해 새로운 수를 만드는 방법을 살펴봅니다. 핵심 조건은 자릿수를 추가하는 매 단계마다 결과 숫자가 다른 수 B로 나누어떨어져야 한다는 점입니다.
예를 들어 기존 숫자에 4개의 자릿수를 더해 5자리 숫자를 만들고, 7로 나누어떨어지는지 검사한다고 가정해 봅시다. 시작 숫자가 8이라면 먼저 4를 붙여 84를 만듭니다. 84는 7로 나누어떨어지므로 조건을 충족합니다. 이후에는 0을 붙여도 7의 배수라는 성질이 유지됩니다(84 × 10 = 840 역시 7로 나누어떨어짐). 따라서 나누어떨어지는 수를 한 번 찾으면, 남은 자릿수는 모두 0으로 채우면 됩니다. 만약 어떤 자릿수를 추가해도 조건을 만족할 수 없다면 -1을 반환합니다.
알고리즘
addNDigits(a, b, n)
begin
num := a
for all number x from 0 to 9, do
temp := a * 10 + x
if temp mod b is 0, then
a := temp
break
end if
done
if num = a, then
return -1
end if
add remaining 0's with a
return a.
end
알고리즘의 원리는 간단합니다. 숫자 a 뒤에 자릿수 x를 붙이면 새로운 값은 a × 10 + x가 됩니다. 따라서 0부터 9까지의 모든 x를 시도해 보며 a × 10 + x가 b로 나누어떨어지는지 확인하고, 조건을 만족하는 첫 번째 x를 붙인 뒤 반복문을 종료합니다. 끝까지 적절한 x를 찾지 못했다면 조건을 만족하는 수를 만들 수 없으므로 -1을 반환합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int add_n_digits(int a, int b, int n) {
int num = a;
for (int i = 0; i <= 9; i++) { // 0~9까지 모든 숫자를 추가해 테스트
int tmp = a * 10 + i;
if (tmp % b == 0) {
a = tmp; // 자릿수 추가 후 a 갱신
break;
}
}
if (num == a) // 자릿수가 추가되지 않았다면 -1 반환
return -1;
for (int j = 0; j < n - 1; j++) // 나누어떨어지는 수를 찾은 뒤 나머지 자릿수는 0으로 채움
a *= 10;
return a;
}
main() {
int a, b, n;
cout << "Enter A, B and N: ";
cin >> a >> b >> n;
int res = add_n_digits(a, b, n);
if(res == -1) {
cout << "Unable to get this type of number";
} else {
cout << "Result is " << res;
}
}
실행 결과
Enter A, B and N: 8 7 4
Result is 84000
A = 8, B = 7, N = 4를 입력한 경우입니다. 첫 단계에서 4를 붙여 84를 만들면 7로 나누어떨어지고, 이후 세 자릿수를 모두 0으로 채워 최종 결과 84000이 출력됩니다.
실행 결과 (생성 실패 사례)
Enter A, B and N: 10 11 5
Unable to get this type of number
A = 10, B = 11인 경우를 살펴보겠습니다. 10 뒤에 0부터 9까지 어떤 한 자리 숫자를 붙여도 101~109 중 어느 수도 11의 배수가 아니므로, 프로그램은 -1을 반환하고 조건을 만족하는 숫자를 만들 수 없다는 메시지를 출력합니다. 이처럼 B의 값에 따라 원하는 형태의 숫자 생성이 불가능할 수 있으며, 이 경우 함수가 -1을 반환하는 것으로 상황을 처리합니다.