C++로 n 이하의 3 또는 7의 배수 개수 구하기

숫자 n이 주어졌을 때, 1부터 n 사이에 존재하는 3 또는 7의 배수가 몇 개인지 구하는 문제입니다. 먼저 예시를 통해 살펴보겠습니다.

예시

입력

출력

1부터 100 사이에는 3 또는 7의 배수가 총 43개 존재합니다.

알고리즘

가장 직관적인 방법은 3부터 n까지 모든 숫자를 하나씩 확인하는 것입니다.

숫자 n을 입력받아 초기화합니다.
배수의 개수를 저장할 변수 count를 0으로 초기화합니다.
3부터 n까지 반복하는 루프를 작성합니다.
- 현재 숫자가 3 또는 7로 나누어 떨어지면(나머지가 0이면) count를 1 증가시킵니다.
루프가 끝나면 count 값을 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int getMultiplesCount(int n) {
    int count = 0;
    for (int i = 3; i <= n; i++) {
        if (i % 3 == 0 || i % 7 == 0) {
            count++;
        }
    }
    return count;
}
int main() {
    cout << getMultiplesCount(100) << endl;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

시간 복잡도 개선: 수학적 접근

위 방법의 시간 복잡도는 O(n)입니다. 하지만 수학적 공식을 활용하면 O(1)의 시간 복잡도로 최적화할 수 있습니다.

핵심 아이디어는 포함-배제 원리(Inclusion-Exclusion Principle)입니다. 3의 배수와 7의 배수를 단순히 더하면 두 수의 공배수인 21의 배수가 중복으로 계산되므로, 이를 한 번 빼주어야 합니다.

#include <bits/stdc++.h>
using namespace std;
int getMultiplesCount(int n) {
    return n / 3 + n / 7 - n / 21;
}
int main() {
    cout << getMultiplesCount(100) << endl;
}

n = 100일 경우, 100/3 = 33개, 100/7 = 14개, 중복된 100/21 = 4개이므로 33 + 14 - 4 = 43이라는 동일한 결과를 얻을 수 있습니다. n이 매우 큰 경우에는 이 방법이 훨씬 효율적입니다.