Problem 001 : Multiples of 3 and 5 (5%)

Description

original

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

간략 해석

1000 미만의 3 또는 5의 배수의 합을 구하는 문제입니다.

Idea & Algorithm

naive idea

수의 범위가 작기때문에 반복문을 통해 3의 배수 또는 5의 배수인 경우 더 해주면 됩니다.

이 경우 반복문 한 번에 다 돌 수 있기 때문에 시간복잡도는 $O(N)$이 됩니다.

advanced idea

기본적인 포함배제 문제입니다.

$[0,SZ)$에서 $n$의 배수는 다음과 같이 표현할 수 있다.

\[n\mathbb{Z} = \left\{ 0,n,2 \cdot n ... \lfloor\frac{SZ-1}{n}\rfloor\cdot n \right\}\]

$T = \lfloor\frac{SZ-1}{n}\rfloor$이라 하면 범위 내의 $n$의 배수의 합을 다음과 같이 정의 할 수 있다.

\[SUM(n\mathbb{Z}) = n\cdot\frac{T\cdot(T+1)}{2}\]

그리고 저희가 구하는 값은 다음과 같이 쓸 수 있습니다.

\[answer = SUM(3\mathbb{Z}) + SUM(5\mathbb{Z}) - SUM(15\mathbb{Z})\]

이 방식으로 할 경우에는 $O(1)$으로 해결할 수 있습니다.

만약 수의 종류가 적당히 많아진다면 뫼비우스 함수로 할 수도 있습니다.

source code

예전 코드라 간략하게 <stdio.h> 헤더만으로 짰다. naive하게 짜도 충분하므로 쉽게 짰다.

#include <stdio.h>

int arr[1005];

int main(){
    int tot = 0;
    for(int i = 1 ; i < 1000 ; i++){
        if(i%3==0||i%5==0) tot += i;
    }
    printf("%d",tot);
}

Problem 001