[Project Euler #1][C++] 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

문제1 : 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

문제

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.

1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

문제 해결 방법

for 문을 사용하여 1이상 1000 미만의 범위에서 해당 수가 3 또는 5로 나누어질 경우, 그 값들의 축적합을 구하도록 프로그램을 구현하였다.

소스 코드

#include <iostream>
using namespace std;
 
#define MAX_NUM 1000
 
int main() {
    int sum = 0;
    
    for (int i = 1; i < MAX_NUM; i++) {
        if ((i % 3 == 0) || (i % 5 == 0)) {                                                                                  
            sum += i;
        }
    }
 
    cout << sum << endl;
 
    return 0;
}

정답

233168

심화 공부

등차급수(Arithmetic Series)

초항이 $a_{1}$ 이고, 공차가 $d$ 인 등차수열의 초항부터 n번째 항까지의 합 $S_{n} = a_{1} + a_{2} + \cdots + a_{n - 1} + a_{n}$ 을 등차급수(Arithmetic Series) 라 하고, 다음 공식으로 구할 수 있다.

$S_{n} = \frac{n(a_{1} + a_{n})}{2} = \frac{n[2a_{1} + (n-1)d]}{2}$

포함배제의 원리(Inclusion-Exclusion Principle)

유한 집합의 합집합의 원소 개수를 세는 기법으로, 2개 또는 3개의 집합의 경우는 각각 다음과 같다.

$\begin{vmatrix}A \cup B \end{vmatrix} = \begin{vmatrix}A\end{vmatrix} + \begin{vmatrix}B\end{vmatrix} - \begin{vmatrix}A  \cap B\end{vmatrix}$

$\begin{vmatrix}A \cup B \cup C\end{vmatrix} = \begin{vmatrix}A\end{vmatrix} + \begin{vmatrix}B\end{vmatrix} + \begin{vmatrix}C\end{vmatrix}- \begin{vmatrix}A \cap B\end{vmatrix} - \begin{vmatrix}A \cap C\end{vmatrix} - \begin{vmatrix}B \cap C\end{vmatrix} + \begin{vmatrix}A \cap B \cap C\end{vmatrix}$

---

문제 출처 : https://euler.synap.co.kr/problem=1