C++로 주어진 범위 내에서 M으로 나누어 떨어지는 숫자 개수 세기

세 개의 정수 A, B, M이 주어졌을 때, A와 B가 정의하는 범위 [A, B] 안에서 M으로 나누어 떨어지는 숫자가 몇 개 있는지 세는 것이 이 문제의 목표입니다.

가장 직관적인 방법은 i를 A부터 B까지 하나씩 증가시키면서, i % M == 0을 만족하는 경우마다 카운트를 늘리는 것입니다.

입력 및 출력 예시

예시 1

입력:

A = 11, B = 20, M = 5

출력:

주어진 범위에서 M으로 나누어 떨어지는 숫자의 개수: 2

설명: 범위 [11, 20] 안에서 5로 나누어 떨어지는 숫자는 15와 20뿐입니다.

예시 2

입력:

A = 20, B = 50, M = 11

출력:

주어진 범위에서 M으로 나누어 떨어지는 숫자의 개수: 3

설명: 범위 [20, 50] 안에서 11로 나누어 떨어지는 숫자는 22, 33, 44입니다.

접근 방법

A, B, M을 정수형으로 입력받습니다.
divisiblebyM(int a, int b, int m) 함수는 A, B, M을 매개변수로 받아 범위 [A, B] 내에서 M으로 나누어 떨어지는 숫자의 개수를 반환합니다.
카운트 변수를 0으로 초기화합니다.
for 반복문으로 i를 A부터 B까지 1씩 증가시키며 순회합니다.
i % m == 0이면 카운트를 1 증가시킵니다.
반복문이 끝나면 카운트에는 범위 내 M의 배수 개수가 저장됩니다.
카운트를 결과로 반환합니다.

C++ 코드 구현

// 주어진 범위에서 M으로 나누어 떨어지는 숫자의 개수를 세는 프로그램
#include <bits/stdc++.h>
using namespace std;

int divisiblebyM(int a, int b, int m){
    int count = 0;
    // A부터 B까지 반복하며 각 숫자가 M으로 나누어 떨어지는지 확인
    for (int i = a; i <= b; i++){
        if (i % m == 0){
            count++;
        }
    }
    return count;
}

int main(){
    // A와 B는 범위를 정의하고, M은 나누는 수(제수)
    int A = 3, B = 15, M = 4;
    cout << "Numbers divisible by M in given range:" << divisiblebyM(A, B, M) << endl;
    return 0;
}

출력 결과

Numbers divisible by M in given range: 3

심화: O(1) 시간 복잡도 최적화 방법

범위가 매우 넓은 경우 위의 반복문 방식(O(B-A+1))은 비효율적일 수 있습니다. 1부터 n까지 M의 배수 개수는 정수 나눗셈으로 n / m과 같으므로, 다음 공식을 사용하면 한 번의 연산으로 답을 구할 수 있습니다.

int divisiblebyM(int a, int b, int m){
    return b / m - (a - 1) / m;
}

이 방법은 시간 복잡도가 O(1)이므로 범위가 클 때 훨씬 효율적입니다. 단, 음수가 포함된 범위에서는 나눗셈 동작이 컴파일러마다 다를 수 있으므로 주의가 필요합니다.