문제 소개
이 문제에서는 세 개의 정수 M1, M2, N이 주어집니다. 우리가 작성해야 할 프로그램은 N 미만에 있는 두 수의 배수들의 합을 구하는 것입니다.
여기서 말하는 배수란 N보다 작으면서 M1 또는 M2로 나누어 떨어지는 모든 수를 의미합니다.
예제로 이해해 보기
입력:
N = 13, M1 = 4, M2 = 6
출력:
30
설명: 13보다 작은 4와 6의 배수는 4, 6, 8, 12입니다. 이들의 합은 4 + 6 + 8 + 12 = 30입니다.
방법 1: 반복문을 이용한 단순 해법
가장 간단한 접근 방식은 1부터 N-1까지 반복하면서 M1 또는 M2로 나누어 떨어지는 값을 모두 더하는 것입니다.
알고리즘
1단계: sum = 0으로 초기화하고, i를 1부터 N-1까지 반복합니다.
1-1단계: 만약 (i % M1 == 0) 또는 (i % M2 == 0)이라면 sum += i를 실행합니다.
2단계: sum을 반환합니다.
구현 예제
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2){
int sum = 0;
for (int i = 0; i < N; i++)
if (i % M1 == 0 || i % M2 == 0)
sum += i;
return sum;
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout << "24 미만의 4와 7의 배수의 합은 " << calcMulSum(N, M1, M2);
return 0;
}
실행 결과
24 미만의 4와 7의 배수의 합은 102
이 방법은 구현이 직관적이지만 시간 복잡도가 O(n)이므로 N이 매우 커지면 비효율적입니다.
방법 2: 수학 공식을 이용한 효율적인 해법
더 나은 해결책은 등차수열의 합 공식을 활용하는 것입니다. 포함-배제 원리에 따라 최종 합은 다음과 같이 계산됩니다.
최종 합 = (M1의 배수의 합) + (M2의 배수의 합) − (M1×M2의 배수의 합)
M1×M2의 배수를 빼는 이유는 두 수의 공통 배수가 중복으로 더해지기 때문입니다.
x의 배수 중 n개 항까지의 합은 다음 공식으로 구할 수 있습니다.
Sum(X) = (n × (n+1) × X) / 2
이 공식을 적용하면 전체 합은 다음과 같이 표현할 수 있습니다.
sum = ((N/M1) × (1 + N/M1) × M1 / 2)
+ ((N/M2) × (1 + N/M2) × M2 / 2)
− ((N/(M1×M2)) × (1 + N/(M1×M2)) × (M1×M2) / 2)
구현 예제
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2){
N--; // N 미만이므로 N-1까지 고려
return (((N/M1) * (1 + (N/M1)) * M1 / 2)
+ ((N/M2) * (1 + (N/M2)) * M2 / 2)
- ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout << "24 미만의 4와 7의 배수의 합은 " << calcMulSum(N, M1, M2);
return 0;
}
실행 결과
24 미만의 4와 7의 배수의 합은 102
마무리
반복문 기반 해법은 O(n)의 시간 복잡도를 가지지만, 수학 공식을 활용한 해법은 곱셈과 나눗셈 몇 번만으로 답을 구할 수 있어 사실상 O(1)의 성능을 보입니다. 따라서 N이 큰 경우에는 수학 공식을 이용한 접근 방식이 훨씬 효율적입니다.