C++로 N 이하의 2, 3, 5의 배수 개수 구하기

이 문제에서는 하나의 자연수 N이 주어지며, 우리의 과제는 N보다 작거나 같은 수 중에서 2, 3 또는 5의 배수를 찾는 것입니다.

문제 설명

핵심은 1부터 N까지의 모든 수 중에서 2, 3 또는 5로 나누어 떨어지는 수의 개수를 구하는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

입력

N = 7

출력

5

설명

1부터 7까지의 수 : 1, 2, 3, 4, 5, 6, 7
2, 3, 5로 나누어 떨어지는 수 : 2, 3, 4, 5, 6 (총 5개)

접근 방법 1: 단순 순회

가장 직관적인 해결 방법은 1부터 N까지 모든 수를 차례대로 확인하면서 2, 3 또는 5로 나누어 떨어지는 수의 개수를 세는 것입니다.

알고리즘

초기화 — count = 0

1단계 — i = 1부터 N까지 반복문을 실행합니다.

1.1단계 — 만약 (i % 2 == 0 || i % 3 == 0 || i % 5 == 0)이라면 count를 1 증가시킵니다.

2단계 — 최종 count 값을 반환합니다.

접근 방법 2: 집합론(포함-배제 원리) 활용

더 효율적인 방법은 집합론의 포함-배제 원리(Inclusion-Exclusion Principle)를 이용하는 것입니다.

먼저 각각의 경우를 다음과 같이 정의합니다.

• n(2), n(3), n(5) : 각각 2, 3, 5로 나누어 떨어지는 수의 개수
• n(2 ∩ 3), n(2 ∩ 5), n(3 ∩ 5) : 두 수의 공통 배수인 수의 개수
• n(2 ∩ 3 ∩ 5) : 2, 3, 5 모두로 나누어 떨어지는 수의 개수

포함-배제 원리에 따라 다음 식이 성립합니다.

n(2 ∪ 3 ∪ 5) = n(2) + n(3) + n(5) − n(2 ∩ 3) − n(2 ∩ 5) − n(3 ∩ 5) + n(2 ∩ 3 ∩ 5)

이 솔루션은 각 숫자 조합에 대한 비트 마스크(bitmask)를 계산하여 효율적으로 구현할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int countMultiples(int n) {
    int values[] = { 2, 3, 5 };
    int countMultiples = 0, bitMask = pow(2, 3);
    for (int i = 1; i < bitMask; i++) {
        int prod = 1;
        for (int j = 0; j < 3; j++) {
            if (i & 1 << j)
                prod = prod * values[j];
        }
        if (__builtin_popcount(i) % 2 == 1)
            countMultiples = countMultiples + n / prod;
        else
            countMultiples = countMultiples - n / prod;
    }
    return countMultiples;
}
int main() {
    int n = 13;
    cout<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl;
    return 0;
}

출력 결과

The number of multiples till 13 is 9