001. Multiples of 3 or 5 (3과 5의 배수들의 합)

​문제 (English)

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.

 

Answer: 233168

문제 분석

---

어떤 수보다 작은 3의 배수 혹은 5의 배수를 찾고 이를 더하라는 건데, 

• 어떤 수의 배수라는 것은 어떤 의미인지,
• 등차수열에 대한 합은 어떻게 구하는지,

를 물어보는 문제이다.

 

쉽게 푼다면, 어떤 수보다 작은 모든 경우에 대해서 3의 배수인지, 5의 배수인지 판단하면서 더해나가면 된다.

그러나, 이렇게 해서는 속도에 문제가 있다. 등차수열의 합 공식을 이용해서 합을 구해야 한다.

 

풀이 1 

---

가장 간단히 생각해 볼 수 있는 풀이 방법이다.

- 3에서부터 시작해서 한계값 n이 되기 전까지 수 i를 증가시키면서,

- i%3==0 혹은 i%5==0이되는 수를 더해 나간다.

 

코드는 아래와 같다. 

#[test]
fn test(){
    assert_eq!(23, get_sum(10));    
    assert_eq!(233168, get_sum(1000));
}

#[cfg(test)]
fn get_sum(bound: u64) -> u64{
    let mut sum = 0;
    for i in 3..bound{
        if i%3==0 || i%5==0{
            sum += i;
        }
    }
    return sum;
}

 

위 코드에서 for 구문으로 3..bound까지, i%3==0 혹은 i%5==5==0 인지 체크하게 했는데, 이 구문을 Rust의 Iterator Adapter를 사용해서 표현할 수도 있다.  달랑 한 줄로 코딩이 끝난다. (실제 속도가 빨라지거나 하진 않는다. 비슷)

fn get_sum1(bound: u64) -> u64{
    (3..bound).filter(|i| i%3==0 || i%5==0).sum()
}

 

풀이 2 

---

풀이1에서는, 대상이 되는 수를 1씩 증가시키면서 3으로 나누어지는지, 5로 나누어지는지를 체크하면서, 해당되는 수를 더해 나갔다. 

수행되는 연산을 고려해보면, n개의 수에 대해 나머지 연산을 2번 수행하고, if 연산을 한 번 수행하게 된다.

 

나머지 연산은, 나눗셈연산이 들어가는 거여서 부담이 될 수 있으니, 나머지 연산이 안 들어가고 덧셈만 들어가는 알고리즘으로 구현해 보자. 

 

알고리즘의 기본 골격은 다음과 같다.

- 3혹은 5의 배수의 합 = 3의 배수 합 + 5의 배수 합 - 15의 배수 합

- k의 배수의 합은,  k에서 시작해서 k씩 더해가며 n이 나오기 전까지의 수를 더하면 된다.

 

위 알고리즘을 코딩해 본다. 여기서 sum_under(k, bound)는, bound까지의 k배수 합을 구하는 함수이다.

#[cfg(test)]
fn get_sum2(bound: u64) -> u64{
    return sum_under(3,bound) + sum_under(5,bound) - sum_under(15,bound);
}

#[cfg(test)]
fn sum_under(k:u64, bound:u64) -> u64 {
    let mut n:u64 = 0;
    let mut sum:u64 = 0;
    loop {
        n += k;
        if n >= bound { break; }
        sum += n;
    }
    return sum;
}

 

이렇게 하면, 나누기 연산이 없이 덧셈 연산만이 있기에, 조금 빨라진다.

 

풀이 3

---

풀이 2까지를 보면, 실제 해당하는 수를 더해가면 합을 구했다. 

실제 더해가면서 합을 구하지 않고, 합 공식을 이용해서 쉽게 구할 수도 있겠다.

 

1000전까지의 3의 배수는 {3,6,9,...,999}, 5의 배수는 {5,10,15,...,995}이다.

3의 배수의 경우 {3,6,9,...,999} = 3 x {1,2,3,...,333} 이다. 이 합은 3 x 333 x (333+1) /2

 

3의 경우는 3 x Sum(1, 999/3)의 합, 5의 경우는 5 x Sum(1, 999/5)이다. 

 

n까지의 k의 배수의 합 공식으로 일반화해보면, 

$ S = k  \frac {p(p+1)} {2}, p = int(\frac {n} {k}) $

 

코드는 아래와 같다. sun_under를 호출할 때 bound-1을 해줬음에 유의하자.

#[cfg(test)]
fn get_sum3(bound: u64) -> u64{
    return sum_under3(3,bound-1) + sum_under3(5,bound-1) - sum_under3(15,bound-1);
}

#[cfg(test)]
fn sum_under3(k:u64, n:u64) -> u64 {
    let p:u64 = n / k;
    return k * p*(p+1) / 2;
}

 

총평

---

전체 코드를 수행해보면, 합 공식을 이용해서 푼 test3이 월등하게 빠름을 알 수 있다. 각 수를 더하지 않고 하나의 수식만을 계산하여 답을 내는 것이니 당연하다. 

 

* test할 때 수행시간을 print 하게 하기 위해 --nocapture 플래그와 함께 cargo를 수행했음에 유의

 

 

hackerrank 사이트에는 test3의 코드처럼 풀어야 타임아웃 발생하지 않고 풀이를 통과할 수 있다. 

 

전체 소스코드

---

p1.rs 

use std::time::Instant;

#[test]
fn test(){
    assert_eq!(23, get_sum(10));    
    assert_eq!(233168, get_sum(1000));

    let s = Instant::now();
    assert_eq!(23331668, get_sum(10000));
    println!("test: {:?}", s.elapsed());
}

#[cfg(test)]
fn get_sum(bound: u64) -> u64{
    let mut sum = 0;
    for i in 3..bound{
        if i%3==0 || i%5==0{
            sum += i;
        }
    }
    return sum;
}

//-----------------------
#[test]
fn test1(){
    assert_eq!(23, get_sum1(10));    
    assert_eq!(233168, get_sum1(1000));

    let s = Instant::now();
    assert_eq!(23331668, get_sum1(10000));
    println!("test1: {:?}", s.elapsed());
}

#[cfg(test)]
fn get_sum1(bound: u64) -> u64{
    (3..bound).filter(|i| i%3==0 || i%5==0).sum()
}

//----------------------------
#[test]
fn test2(){
    assert_eq!(23, get_sum2(10));    
    assert_eq!(233168, get_sum2(1000));

    let s = Instant::now();
    assert_eq!(23331668, get_sum2(10000));
    println!("test2: {:?}", s.elapsed());
}

#[cfg(test)]
fn get_sum2(bound: u64) -> u64{
    return sum_under(3,bound) + sum_under(5,bound) - sum_under(15,bound);
}

#[cfg(test)]
fn sum_under(k:u64, bound:u64) -> u64 {
    let mut n:u64 = 0;
    let mut sum:u64 = 0;
    loop {
        n += k;
        if n >= bound { break; }
        sum += n;
    }
    return sum;
}


//----------------------------
#[test]
fn test3(){
    assert_eq!(23, get_sum3(10));    
    assert_eq!(233168, get_sum3(1000));

    let s = Instant::now();
    assert_eq!(23331668, get_sum3(10000));
    println!("test2: {:?}", s.elapsed());
}

#[cfg(test)]
fn get_sum3(bound: u64) -> u64{
    return sum_under3(3,bound-1) + sum_under3(5,bound-1) - sum_under3(15,bound-1);
}

#[cfg(test)]
fn sum_under3(k:u64, n:u64) -> u64 {
    let p:u64 = n / k;
    return k * p*(p+1) / 2;
}

 

끝