문제 (English)
The sum of the squares of the first ten natural number is,
$1^2 + 2^2 + ...+10^2 = 385$
The square of the sum of the first ten natural number is,
$(1+2+...+10)^2 = 55^2 = 3025 $
Hence the difference between the sum of the squares of the first ten natural numbers and the sqrare of the sum is $3025-385=2640$.
Fine the difference between the sum of the squares of the first one hundread natural numbers and the square ot the sum.
Answer: 25164150
문제 분석
제곱의 합과, 합의 제곱의 차를 구하는 문제.
합공식을 알고 있다면 쉽게 풀수 있는 문제이다.
1에서 n까지의 합 S는,
$ S = 1+2+...+n = \frac {n(n+1)}{2}$
제곱의 합은,
$S = 1^2 + 2^2 +..._+n^2 = \frac {n(n+1)(2n+1)}{6}$
풀이 1
단순 합 공식은 알고 있어서 공식으로 풀고, 제곱의 합의 그냥 루프를 돌려서 풀어 본다.
#[test]
fn test(){
assert_eq!(0, answer(1));
assert_eq!(4, answer(2));
assert_eq!(22, answer(3));
assert_eq!(2640, answer(10));
assert_eq!(25164150, answer(100));
}
#[cfg(test)]
//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
fn answer(n: u64) -> u64{
//1. a = (1+...+100)^2
let mut a: u64 = get_seq_sum(n);
a = a.pow(2);
//2. b = (1^2 + ... +100^2)
let b: u64 = get_square_sum(n);
//3. a-b
a - b
}
#[cfg(test)]
fn get_seq_sum(n: u64) -> u64{
n * (n+1) / 2
}
#[cfg(test)]
fn get_square_sum(n: u64) -> u64{
let mut sum: u64 = 0;
for i in 1..=n {
sum += i.pow(2);
}
return sum;
}
이렇게 해도 hackerrank 통과한다.
풀이 2
제곱수에 대한 합도 공식을 이용해서 푼다.
fn get_square_sum1(n: u64) -> u64{
n*(n+1)*(2*n+1)/6
}
총평
u32말고 u64로 사용하고, 공식만을 알면 쉽게 풀 수 있는 문제
전체 소스코드
p6.rs
/// - 공식을 사용해서 계산하는 것이 제일 빠르다.
/// 1)연속된 자연수의 합 공식
/// 2)연속된 자연수제곱의 합 공식
/// - 그 다음은 그냥 원시적으로 루프에 의해서 계산하는 것
/// - (a+b)^2 = a^2 + b^2 -2ab를 이용해서 푸는 것은, 오히려 계산량이 더 많다.
///
#[test]
fn test(){
assert_eq!(0, answer(1));
assert_eq!(4, answer(2));
assert_eq!(22, answer(3));
assert_eq!(2640, answer(10));
assert_eq!(25164150, answer(100));
}
#[cfg(test)]
//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
fn answer(n: u64) -> u64{
//1. a = (1+...+100)^2
let mut a: u64 = get_seq_sum(n);
a = a.pow(2);
//2. b = (1^2 + ... +100^2)
let b: u64 = get_square_sum(n);
//3. a-b
a - b
}
#[cfg(test)]
fn get_seq_sum(n: u64) -> u64{
n * (n+1) / 2
}
#[cfg(test)]
fn get_square_sum(n: u64) -> u64{
let mut sum: u64 = 0;
for i in 1..=n {
sum += i.pow(2);
}
return sum;
}
//-----------------
// use (1^2 + ... +n^2) = n(n+1)(2n+1)/6
#[test]
fn test1(){
assert_eq!(0, answer1(1));
assert_eq!(4, answer1(2));
assert_eq!(22, answer1(3));
assert_eq!(2640, answer1(10));
assert_eq!(25164150, answer1(100));
}
//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
#[cfg(test)]
fn answer1(n: u64) -> u64{
//1. a = (1+...+100)^2
let mut a: u64 = get_seq_sum(n);
a = a.pow(2);
//2. b = (1^2 + ... +100^2)
let b: u64 = get_square_sum1(n);
//3. a-b
a - b
}
//공식유도는 euler #6 설명 pdf 참조
#[cfg(test)]
fn get_square_sum1(n: u64) -> u64{
n*(n+1)*(2*n+1)/6
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
008. Largest Product in a Series (문자열에서 k자리씩 짤라서 수를 만들고 곱셈하기) (0) | 2024.08.13 |
---|---|
007. 10001st Prime (k번째 소수 구하기) (0) | 2024.08.13 |
005. Smallest Multiple (여러 수에 대한 최소공배수 구하기) (0) | 2024.08.13 |
004. Largest Palindrome Product (가장 큰 대칭수 찾기) (0) | 2024.08.12 |
003. Largest Prime Factor (어떤 수에 대한 가장 큰 소인수 구하기) (0) | 2024.08.12 |