문제 개요
두 개의 값, 즉 자릿수(digit)와 기준이 되는 수(num)가 주어졌을 때, num으로 나누어 떨어지는 digit자리 숫자의 개수를 구하는 것이 목표입니다.
쉽게 말해, 예를 들어 digit에 2가 입력되면 먼저 모든 두 자리 숫자(10~99)를 생각한 뒤, 그중 num으로 나누어 떨어지는 수의 개수를 세면 됩니다.
구체적인 예시를 통해 문제를 더 자세히 이해해 보겠습니다.
예시 입력 및 출력
입력 − digit = 2, num = 12
출력 − 주어진 수로 나누어 떨어지는 n자리 숫자의 개수: 8
설명 − 12로 나누어 떨어지는 두 자리 숫자는 12, 24, 36, 48, 60, 72, 84, 96으로 총 8개입니다.
입력 − digit = 2, num = 9
출력 − 주어진 수로 나누어 떨어지는 n자리 숫자의 개수: 10
설명 − 9로 나누어 떨어지는 두 자리 숫자는 18, 27, 36, 45, 54, 63, 72, 81, 90, 99로 총 10개입니다.
알고리즘 접근 방식
- digit과 num을 입력받습니다.
- 나누어 떨어지는 숫자의 개수를 저장할 변수 count를 0으로 초기화합니다.
- digi_first를 pow(10, digit - 1)로 설정합니다. 이는 digit자리 숫자 중 가장 작은 값입니다.
- digi_last를 pow(10, digit)로 설정합니다. 이는 digit자리 숫자 범위의 바로 다음 값, 즉 상한값입니다.
- d_first를 digi_first % num으로, d_last를 digi_last % num으로 계산합니다.
- d_first와 d_last를 구한 뒤, digi_first를 (digi_first - d_first) + num으로, digi_last를 digi_last - d_last로 갱신합니다. 이 과정을 거치면 digi_first는 범위 내에서 num으로 나누어 떨어지는 가장 작은 수가 되고, digi_last는 가장 큰 수가 됩니다.
- count를 ((digi_last - digi_first) / num + 1)로 설정합니다. 두 경계값이 모두 num의 배수이므로, 그 차이를 num으로 나눈 후 1을 더하면 포함 범위 안에 있는 배수의 총 개수를 구할 수 있습니다.
- count를 반환하고 출력합니다.
예제 코드
#include <cmath>
#include <iostream>
using namespace std;
int main(){
int digit = 2, num = 9;
// 나누어 떨어지는 숫자의 개수를 저장
int count = 0;
int digi_first = pow(10, digit - 1); // digit자리 숫자의 최솟값
int digi_last = pow(10, digit); // digit자리 숫자의 상한값
int d_first = digi_first % num;
int d_last = digi_last % num;
digi_first = (digi_first - d_first) + num; // 범위 내 첫 번째 배수
digi_last = digi_last - d_last; // 범위 내 마지막 배수
count = ((digi_last - digi_first) / num + 1);
cout<<"주어진 수로 나누어 떨어지는 n자리 숫자의 개수: "<<count<<"\n";
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
주어진 수로 나누어 떨어지는 n자리 숫자의 개수: 10
복잡도 분석
이 방법은 반복문 없이 나머지 연산과 나눗셈 같은 산술 연산만 사용하므로 시간 복잡도는 O(1)입니다. 따라서 자릿수가 커져도 일정한 시간 안에 빠르게 결과를 계산할 수 있다는 장점이 있습니다.