보통은 %(나머지) 연산자를 사용하면 어떤 수가 3이나 5의 배수인지 손쉽게 확인할 수 있습니다. 하지만 이번 문제에서는 % 연산자를 사용할 수 없다는 조건이 붙어 있습니다.
여기서 해답이 되는 것은 바로 + 연산자입니다. 배수는 일정한 간격으로 커지기 때문에, 이전 배수에 3 또는 5를 더하기만 하면 다음 배수를 차례로 구할 수 있습니다.
문제 예시
입력
15
출력
1 2 3 - Multiple of 3 4 5 - Multiple of 5 6 - Multiple of 3 7 8 9 - Multiple 3 10 - Multiple of 5 11 12 - Multiple of 3 13 14 15 - Multiple of both 3 and 5
알고리즘
- 숫자 n을 초기화합니다.
- 3의 다음 배수와 5의 다음 배수를 추적할 두 개의 변수를 준비합니다.
- 처음에는 이 두 변수를 각각 3과 5로 설정합니다.
- 1부터 n까지(양 끝 포함) 반복하는 루프를 작성합니다.
- 추적 변수와 현재 숫자를 비교하여 3의 배수인지 확인합니다.
- 같은 방식으로 5의 배수인지도 확인합니다.
- 배수라면 해당 값(3 또는 5)을 더해 다음 배수를 미리 계산해 둡니다.
- 판별 결과에 맞는 문구를 콘솔에 출력합니다.
C++ 구현
위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void findMultiplesOf3And5(int n) {
int threeMultiple = 3; // 다음 3의 배수
int fiveMultiple = 5; // 다음 5의 배수
for (int i = 1; i <= n; i++) {
bool _3 = false, _5 = false;
if (i == threeMultiple) {
threeMultiple += 3;
_3 = true;
}
if (i == fiveMultiple) {
fiveMultiple += 5;
_5 = true;
}
if (_3 && _5) {
cout << "Multiple of both 3 and 5" << endl;
} else if (_3) {
cout << "Multiple of 3" << endl;
} else if (_5) {
cout << "Multiple of 5" << endl;
} else {
cout << i << endl;
}
}
}
int main() {
findMultiplesOf3And5(100);
return 0;
}코드 동작 원리
threeMultiple 변수는 앞으로 등장할 3의 배수를, fiveMultiple 변수는 앞으로 등장할 5의 배수를 미리 기억하고 있습니다. 루프가 진행되면서 현재 숫자 i가 이 변수들과 일치하면 해당 숫자는 배수로 판정되고, 추적 변수는 자신의 값만큼 증가하여 다음 배수를 가리키게 됩니다. 이 방식은 나눗셈 없이 덧셈과 비교만으로 배수를 판별하며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다. (아래는 30까지의 결과이며, 실제 실행 시에는 100까지 계속 출력됩니다.)
1 2 Multiple of 3 4 Multiple of 5 Multiple of 3 7 8 Multiple of 3 Multiple of 5 11 Multiple of 3 13 14 Multiple of both 3 and 5 16 17 Multiple of 3 19 Multiple of 5 Multiple of 3 22 23 Multiple of 3 Multiple of 5 26 Multiple of 3 28 29 Multiple of both 3 and 5 ...