이 글에서는 1부터 n(주어진 값)까지의 숫자 중, 2부터 10 사이의 어떤 수로도 나누어 떨어지지 않는 숫자를 찾는 문제를 다룹니다. 먼저 예시를 통해 문제를 이해해 보겠습니다.
입력 : num = 14 출력 : 3 설명 : 1, 11, 13 세 개의 숫자는 2~10 사이의 어떤 수로도 나누어 떨어지지 않습니다. 입력 : num = 21 출력 : 5 설명 : 1, 11, 13, 17, 19 다섯 개의 숫자가 해당됩니다.
문제 해결 접근 방식
단순한 방법
1부터 num까지의 모든 숫자에 대해 2~10 사이의 어떤 수로 나누어 떨어지는지 하나씩 확인하고, 나누어 떨어지지 않으면 카운트를 증가시키는 방법입니다. 하지만 이 방식은 모든 숫자를 일일이 검사해야 하므로 실행 시간이 오래 걸리고 시간 복잡도가 크게 증가한다는 단점이 있습니다.
효율적인 방법
더 효율적인 접근은, 먼저 1부터 num까지의 숫자 중 [2, 10] 범위의 어떤 수로든 나누어 떨어지는 숫자의 개수를 구한 뒤, 전체 개수 num에서 그 값을 빼는 것입니다.
그렇다면 2, 3, 4, 5, 10으로 나누어 떨어지는 모든 숫자를 찾아야 할까요? 사실 그럴 필요가 없습니다. 4, 6, 8, 10으로 나누어 떨어지는 숫자는 항상 2로도 나누어 떨어지고, 6과 9로 나누어 떨어지는 숫자는 3으로도 나누어 떨어지기 때문입니다.
결국 우리는 2, 3, 5, 7로 나누어 떨어지는 숫자의 개수만 구하면 되며, 이는 포함-배제 원리(Inclusion-Exclusion Principle)를 이용해 계산할 수 있습니다.
포함-배제 원리란?
포함-배제 원리는 각 단일 집합의 크기는 더하고, 두 집합씩 짝지은 교집합의 크기는 빼고, 세 집합의 교집합의 크기는 다시 더하는 식으로 교집합의 중복 계산을 보정하는 원리입니다.
이를 공식으로 나타내면 다음과 같습니다.
= NUM − X + Y − Z + A.
각 항의 의미는 다음과 같습니다.
X = 2, 3, 5, 7 각각으로 나누어 떨어지는 수
( [num / 2] + [num / 3] + [num / 5] + [num / 7] )
Y = (2,3), (2,5), (2,7), (3,5), (3,7), (5,7) 쌍으로 나누어 떨어지는 수
( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)]
+ [num / (3 * 5)] + [num / (3 * 7)] + [num / (5 * 7)] )
Z = (2,3,5), (2,3,7), (2,5,7), (3,5,7)으로 나누어 떨어지는 수
( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)]
+ [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )
A = (2, 3, 5, 7) 모두로 나누어 떨어지는 수
( [num / (2 * 3 * 5 * 7)] )C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 21, result;
// 포함-배제 원리의 공식을 적용하여
// 2~10 사이의 어떤 수로도 나누어 떨어지지 않는 숫자의 개수를 구합니다.
result = n - n / 2 - n / 3 - n / 5 - n / 7
+ n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
- n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
cout << "[2, 10]으로 나누어 떨어지지 않는 숫자의 개수: " << result;
return 0;
}실행 결과
[2, 10]으로 나누어 떨어지지 않는 숫자의 개수: 5
마무리
이 글에서는 1부터 n까지의 숫자 중 2~10 사이의 어떤 수로도 나누어 떨어지지 않는 숫자를 찾는 방법을 살펴보았습니다. 포함-배제 원리를 활용하면 반복문 없이 단순한 산술 연산만으로 결과를 구할 수 있어 O(1)의 시간 복잡도를 달성할 수 있습니다. 소개한 로직은 Java, C, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.