문제 개요
두 개의 정수 m과 n이 주어졌을 때, n으로 나누어 떨어지는 m자리 숫자가 몇 개인지 구하는 것이 이 글의 목표입니다.
간단한 예로 m=1이라면 대상 숫자는 0부터 9까지이고, n=3일 때 3으로 나누어 떨어지는 수는 0, 3, 6, 9로 총 4개입니다.
예제로 이해하기
입력 — m=2, n=9
출력 — n으로 나누어 떨어지는 m자리 수의 개수: 10
설명 — 10부터 99 사이에서 9로 나누어 떨어지는 수는 다음과 같습니다.
18, 27, 36, 45, 54, 63, 72, 81, 90, 99
입력 — m=3, n=300
출력 — n으로 나누어 떨어지는 m자리 수의 개수: 3
설명 — 100부터 999 사이에서 300으로 나누어 떨어지는 수는 다음과 같습니다.
300, 600, 900
풀이 접근 방법
- 정수 m과 n을 입력받습니다.
- (m-1)자리 수 중 가장 큰 값을 num1로 계산합니다.
- m자리 수 중 가장 큰 값을 num2로 계산합니다.
- findCount(int n, int L, int R) 함수는 n과 범위(num1+1 ~ num2)를 입력받아 해당 범위 안에서 n으로 나누어 떨어지는 모든 수의 개수를 반환합니다.
- 초기 count 값은 0으로 설정합니다.
- i를 L부터 R까지 반복하면서 i % n == 0이면 count를 1씩 증가시킵니다.
- 최종 count를 결과로 반환합니다.
C++ 코드 예제
#include<bits/stdc++.h>
using namespace std;
// n을 약수로 가지는 m자리 수의 개수를 반환
int findCount(int n, int L, int R){
int count=0;
int i;
for(int i=L;i<=R;i++){
if(i%n==0)
{ count++; }
}
return count;
}
int main(){
int M = 2, N = 9;
int i;
int num1 = 0; // (m-1)자리 수 중 최대값
for (i = 0; i < (M - 1); i++)
num1 = (num1 * 10) + 9;
int num2 = 0; // m자리 수 중 최대값
for (i = 0; i < M; i++)
num2 = (num2 * 10) + 9;
cout<<"Count of M digit no.s divisible by N:"<<findCount(N,num1+1,num2);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of M digit no.s divisible by N:10
더 효율적인 방법: O(1) 공식 활용
위 방식은 범위 내 모든 수를 하나씩 검사하므로 시간 복잡도가 O(R-L)입니다. 하지만 나눗셈의 성질을 이용하면 반복문 없이 상수 시간에 답을 구할 수 있습니다.
범위 [L, R]에서 n으로 나누어 떨어지는 수의 개수는 다음 공식으로 계산됩니다.
count = (R / n) - ((L - 1) / n)
여기서 L은 num1+1, R은 num2이므로, C++의 정수 나눗셈 특성(소수점 버림)을 활용해 아래와 같이 한 줄로 처리할 수 있습니다.
int count = (num2 / N) - (num1 / N);
이 방법은 m이 커져도 즉시 결과를 얻을 수 있어 실무에서 훨씬 유용합니다. 다만 매우 큰 m에 대해서는 자료형 오버플로우에 유의해야 하며, 필요하다면 long long 타입을 사용하는 것이 좋습니다.