문제 (English)
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be $1+2+3+4+5+6+7=28$. The first ten terms would be:
$1,3,6,10,15,21,28,36,45,55,...$
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7, 21
28: 1,2,4,7, 14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?.
Answer: 76576500
문제 분석
자연수 n까지의 연속된 합을 삼각수(Triangle number)라고 한다. 예를 들어 2까지 합은 3, 3까지 합은 6, 4까지의 합은 10, ...
이 삼각수에 대해서 약수의 개수를 구하라는 문제이다. 정확하게는 약수의 개수가 500개를 넘어서게되는 최초의 삼각수를 구하는 문제.
삼각수야 자연수를 계속 더하면 쉽게 구할 수 있는 것이고, 문제는 약수의 개수를 어떻게 효율적으로 알아낼 것이냐가 핵심.
단순하게는 삼각수 P보다 작은 자연수 모두에 대해서 P를 나누는지(약수인지)를 검사해보는건데, 이렇게하면 hackerrank 사이트를 통과하지 못한다. 타임아웃이 발생한다.
좀 더 생각해서, 나누는 자연수 대상을 $\sqrt{P}$까지만 하고, 구한 약수의 2배를 하는 것도 생각할 수 있는데, 이렇게해도 그닥 효율적이진 않다.
소인수분해를하고, 해당 소인수들의 지수승으로부터 약수의 개수를 구하는 방식이 가장 낫다.
예를들어 72를 소인수분해하면 $2^3 \times 3^2$. 약수의 개수는 $(3+1) \times (2+1)=12$
풀이 1
타임아웃이 발생하겠지만, 약수를 구할 대상이되는 수보다 작은 모든 수로 나눠보는 프로그램을 짜보자.
1) 자연수 i를 증가시키면서 삼각수를 구한다.
2) 삼각수 n에 대한 약수의 개수를 구한다.
2-1)자연수 j를 $\sqrt{n}$까지 증가시키면서 루프를 돈다.
2-2) 루프내에서 n%j==0이면 cnt += 2
2-3) 루프를 벗어나서, $\sqrt{n}$이 자연수이면 cnt -= 1 한다.
3)약수의 개수가 limit보다 커질때의 삼각수가 답이다.
8에 대한 약수를 구한다고 생각해보면, 답은 {1,2,4,8}이 되겠다.
8에 대한 제곱근 정수형은 2.
1에서 2까지에 대해 8에 대해 나눠떨어지는지 검사하면, 둘 다 나눠떨어지기에 2개이고, 1과 2 각각에 대해 $\sqrt{8}$보다 큰 영역에서 대응되는 값 {4,8}이 존재할 것이기에, 전체 cnt=4가 된다.
이러한 이유로 2-1)에서 $\sqrt{n}$까지만 약수가되는지 조사해도 충분한 것.
2-3)에서 cnt를 하나 감소 시킨 것은, 16과 같은 제곱수의 경우 때문이다.
16의 약수는 {1,2,4,8,16}.
$\sqrt{16}=4$이기에 1~4까지 약수를 조사하면 {1,2,4}
cnt=3이기에 이것에 2배를 하면 6개가 된다. $\sqrt{16}=4$에 해당하는 것에도 2배를 곱해줘서 발생하는 오류다. 따라서, 16, 25, 36과 같은 제곱수에 대해서는 cnt를 하나 빼줘야 한다.
코드는,
#[test]
fn test(){
assert_eq!(3, answer(1));
assert_eq!(6, answer(2));
assert_eq!(6, answer(3));
assert_eq!(28, answer(4));
assert_eq!(28, answer(5));
assert_eq!(76576500, answer(500));
assert_eq!(842161320, answer(1000));
}
#[cfg(test)]
fn answer(limit: u32) -> u32{
let mut i:u32 =1;
let mut cnt:u32 = 0;
let mut sum:u32 = 0;
while cnt <= limit {
sum += i;
cnt = count_divisors(sum);
i += 1;
}
return sum;
}
#[cfg(test)]
fn count_divisors(n: u32) -> u32 {
if n == 1 {return 1;}
let sqrt_n = (n as f64).sqrt() as u32;
let mut cnt:u32 = 0;
for i in 1..=sqrt_n {
if n%i == 0 {cnt += 2;}
}
//sqrt(n)이 정수이면 위 루프에서 제곱수에 대해 2개더했기에, cnt를 하나 빼줘야함.
if sqrt_n>1 && sqrt_n*sqrt_n == n { cnt -= 1; }
return cnt;
}
이렇게하면 답은 잘 나오는데, 큰 값에 대해서는 수행속도에 문제가 있다. 이 코드로는 hackerrank 사이트 문제를 통과하지 못한다.
풀이 2
풀이1에서는 약수를 구하는 것을, 실제 값으로 나눠가면서 약수가 되는지를 조사했다. 약수의 개수가 m개 이상이되는 삼각수를 찾는 문제이기에, 후보가되는 수 n에 대해서 $\sqrt{n}$ 만큼 나눗셈을 해야한다. 조사하는 삼각수의 개수를 p라하고, 해당 후보 삼각수의 크기를 q라하면, 알고리즘 복잡도는 pq정도 된다. 즉, 대략 $O(N^2)$ 알고리즘
풀이 2에서는 소인수분해를하고 그로부터 약수의 개수를 구하는 공식을 이용한다. 초등 혹은 중학교때 배웠던 공식이다.
- 어떤 정수 N을 소인수 분해한 것이 $p_1^{e_1} \times p_2^{e_2} \times ... \times p_n^{e_n}$이면,
- 정수 N에 대한 약수의 개수는 $e_1 \times e_2 \times ... \times e_n$
정수 n에 대해 소인수를 구하는 것은, i=2부터 시작해서 증가시키면서 n%i==0이 될때의 i값들을 찾으면 된다. n%i==0이 되는 i값을 찾은 후에는 n /= i를 해서 n 값을 갱신시킨다. 만약 n%i !=0이면 i를 하나 더 증가시키면서 만족하는 i를 찾는다.
이러한 루프를 n>1일 때 계속 진행.
n=12의 경우를 예로 들어보면,
2로 나눠떨어지기에 이 때 i=2가 첫번째 소인수가 된다.
n=12/2=6으로 갱신되고, 이 6에 대해 다시 i=2일 때 나눠떨어지기에 2가 다시 소인수가되고, 이미 2가 있기에 $2^2$이 된다.
n=6/2=3으로 갱신되고, n=3에 대해 i=2일 때 나눠떨어지지 않아서, i=3에서 시도해본다. i=3일 때 나눠 떨어지기에 i=3이 소인수가 됨.
n=3/3=1로 갱신되고, n=1이 되기에 알고리즘 종료
아래는 코드. 소인수를 찾아가면서, 해당 소인수가 이미 있으면 지수를 증가시키는 방법을 썼다. 이를 위해 Hashtable 사용
코드는, 위 풀이 1에서 count_divisors 함수 부분만 다르다.
fn count_divisors1(mut n: u32) -> u32 {
if n <= 1 {return 1;}
if n == 2 || n == 3 {return 2;}
let sqrt_n: u32 = (n as f64).sqrt() as u32;
//1. generate prime factors and exp values
// and save the prime numbers
let mut primes: std::collections::HashMap<u32,u32> = std::collections::HashMap::new();
for i in 2..=sqrt_n {
while n % i == 0 {
if primes.contains_key(&i) {
primes.insert(i as u32, primes[&i]+1);
}else{
primes.insert(i, 1);
}
n /= i;
}
}
if n != 1 {
primes.insert(n, 1);
}
//2. calucalate (e1 +1) * (e2 +1) ...
let mut cnt: u32 = 1;
for i in primes.values() {
cnt *= i + 1;
}
return cnt;
}
이 코드로도 hackerrank 문제를 통과하지 못한다. 타임아웃이 발생한다.
이유는, 소인수가 이미 존재하는지 Hashtable 값을 조사하고, 존재한다면 지수값을 Hashtable에 집어넣는 오버헤드가 있기 때문.
풀이3에서는 Hashtable없이 바로 지수승을 이용해서 약수를 구하는 방법을 사용한다. 이렇게하면 타임아웃없이 문제를 통과할 수 있다.
풀이 3
풀이 2에서 Hashtable이용해서 소인수의 지수승을 담아두고 사용한 것을, Hashtable없이 바로 지수승을 이용해서 약수를 구하는 방법을 쓸 것이다.
n=12의 경우로 생각해보면, 소인수분해하면 $2^2 \times 3$이다.
알고리즘에서 동작되는 것을 생각해보면, n=12에 대해 i=2에 나눠 떨어지니, 소인수가 {2}가되고, n=12/2=6이되면 다시 i=2로 나눠떨어지기에 소인수가 ${2^2}$가 된다. 이제 n=6/2=3이되서, 이제는 i=2로 나눠떨어지지 않는다.
즉, 어떤 n이 있을 때, i값으로 나눠 떨어질때까지 계속해서 try를 해보면, 해당 i값에 대한 지수승을 알 수 있는것.
for i in 2..=sqrt_n {
let mut exp = 1;
while n % i == 0 {
exp += 1;
n /= i;
}
if exp > 1 { cnt *= exp; }
if n==1 { break; }
}
이렇게 구한 소인수의 지수승을 계속 곱해나가면 cnt를 구할 수 있는 것이다.
이렇게 구현한 count_divisors 함수는 아래와 같고, for 루프를 벗어났을 때 n != 1이 아닐 때 cnt *= 2를 한 것에 유의.
for 루프를 벗어났을 때 n != 1이 되는 경우는 n=14와 같은 경우.
14에 대한 소인수분해 값은 $2 \times 7$
n=14에 대해 i=2일 때 나눠 떨어지고, n=14/2=7로 갱신.
n=7에 대해 i <= sqrt(14) 까지의 i값으로 나눠떨어지는 것이 없기에 for 루프를 벗어남. 이 때 n은 그대로 7로 남아 있음.
즉, 실제 소인수분해 값이 $2 \times 7$인데, 위 로직으로는 {2}만 소인수로 찾은 상태.
따라서, 이러한 n != 1인 경우는 마지막 남은 n 값을 소인수로 취급해줘야하고, 이때의 (지수승 + 1) = 2를 cnt에 곱해줘야 하는 것임.
fn count_divisors2(mut n: u32) -> u32 {
if n <= 1 {return 1;}
if n == 2 || n == 3 {return 2;}
let sqrt_n: u32 = (n as f64).sqrt() as u32;
//1. generate prime factors and exp values
let mut cnt: u32 = 1;
for i in 2..=sqrt_n {
let mut exp = 1;
while n % i == 0 {
exp += 1;
n /= i;
}
if exp > 1 { cnt *= exp; }
if n==1 { break; }
}
if n != 1 { // n=14의 경우. 14=2*7 이어서 n=7에서 for루프 벗어남. 해서 7의 지수 1에 대한 곱을 해줌
cnt *= 2;
}
return cnt;
}총평
소인수분해를 하고, 소인수의 지수승에 의해 약수의 개수를 구하는 방식을 써야 타임아웃이 안나고 문제를 통과할 수 있다.
소인수를 찾는 방법은 문제에서 계속 나오는 것이기에, 소인수를 구하는 코드는 익숙하게 알아야한다.
소인수를 찾을 때는 소수를 이미 알고 있다면, 이 소수만을 해당 수에 나눠가면서 구하면 더 빨리 소인수를 찾을 수 있겠다.
그러나, 어느만큼의 소수를 써야하는지를 모르는 상태에서는, 그냥 2부터 시작하는 자연수에 대해 계속 나눠가면서 소인수를 찾는것이 더 낫다.
삼각수에 대한 고찰
삼각수 sum은 자연수 n까지의 합이다. 따라서 자연수 i에서의 삼각수는 $sum = \frac {i(i+1)} {2}$로 계산할 수 있고, 알고리즘에서 i를 증가시키면서 이 공식으로 삼각수를 구할 수 있다.
그러나, 이 문제에서 굳이 이 공식을 사용해서 삼각수를 구할 필요는 없겠다. 어차피 i를 증가시키는 루프는 돌아야하고, 루프를 돌면서 sum += i를 통해서 덧셈연산 한번을 통해 구할 수 있기 때문이다.
전체 소스코드
p12.rs
#[test]
fn test(){
assert_eq!(3, answer(1));
assert_eq!(6, answer(2));
assert_eq!(6, answer(3));
assert_eq!(28, answer(4));
assert_eq!(28, answer(5));
assert_eq!(76576500, answer(500));
assert_eq!(842161320, answer(1000));
}
#[cfg(test)]
fn answer(limit: u32) -> u32{
let mut i:u32 =1;
let mut cnt:u32 = 0;
let mut sum:u32 = 0;
while cnt <= limit {
sum += i;
cnt = count_divisors(sum);
i += 1;
}
return sum;
}
#[cfg(test)]
fn count_divisors(n: u32) -> u32 {
if n == 1 {return 1;}
let sqrt_n = (n as f64).sqrt() as u32;
let mut cnt:u32 = 0;
for i in 1..=sqrt_n {
if n%i == 0 {cnt += 2;}
}
//sqrt(n)이 정수이면 위 루프에서 제곱수에 대해 2개더했기에, cnt를 하나 빼줘야함.
if sqrt_n>1 && sqrt_n*sqrt_n == n { cnt -= 1; }
return cnt;
}
//---------------------------------------------
// count_divisors 함수만 변경
// 소인수분해 이용: 12 = 2^2 * 3 -> (2+1) * (1+1) = 6개
//
#[test]
fn test1(){
assert_eq!(3, answer1(1));
assert_eq!(6, answer1(2));
assert_eq!(6, answer1(3));
assert_eq!(28, answer1(4));
assert_eq!(28, answer1(5));
assert_eq!(76576500, answer1(500));
assert_eq!(842161320, answer1(1000));
}
#[cfg(test)]
fn answer1(limit: u32) -> u32{
let mut i:u32 =1;
let mut cnt:u32 = 0;
let mut sum:u32 = 0;
while cnt <= limit {
sum += i;
cnt = count_divisors1(sum);
i += 1;
}
return sum;
}
#[cfg(test)]
fn count_divisors1(mut n: u32) -> u32 {
if n <= 1 {return 1;}
if n == 2 || n == 3 {return 2;}
let sqrt_n: u32 = (n as f64).sqrt() as u32;
//1. generate prime factors and exp values
// and save the prime numbers
let mut primes: std::collections::HashMap<u32,u32> = std::collections::HashMap::new();
for i in 2..=sqrt_n {
while n % i == 0 {
if primes.contains_key(&i) {
primes.insert(i as u32, primes[&i]+1);
}else{
primes.insert(i, 1);
}
n /= i;
}
}
if n != 1 {
primes.insert(n, 1);
}
//2. calucalate (e1 +1) * (e2 +1) ...
let mut cnt: u32 = 1;
for i in primes.values() {
cnt *= i + 1;
}
return cnt;
}
//---------------------------------------------
// - count_divisors 함수만 변경
// - 소인수분해 이용: 12 = 2^2 * 3 -> (2+1) * (1+1) = 6개
// - 지수를 저장하지 않고, 그대로 곱해서 답 구함
#[test]
fn test2(){
assert_eq!(3, answer2(1));
assert_eq!(6, answer2(2));
assert_eq!(6, answer2(3));
assert_eq!(28, answer2(4));
assert_eq!(28, answer2(5));
assert_eq!(76576500, answer2(500));
assert_eq!(842161320, answer2(1000));
}
#[cfg(test)]
fn answer2(limit: u32) -> u32{
let mut i:u32 =1;
let mut cnt:u32 = 0;
let mut sum:u32 = 0;
while cnt <= limit {
sum += i;
cnt = count_divisors2(sum);
i += 1;
}
return sum;
}
#[cfg(test)]
fn count_divisors2(mut n: u32) -> u32 {
if n <= 1 {return 1;}
if n == 2 || n == 3 {return 2;}
let sqrt_n: u32 = (n as f64).sqrt() as u32;
//1. generate prime factors and exp values
let mut cnt: u32 = 1;
for i in 2..=sqrt_n {
let mut exp = 1;
while n % i == 0 {
exp += 1;
n /= i;
}
if exp > 1 { cnt *= exp; }
if n==1 { break; }
}
if n != 1 { // n=14의 경우. 14=2*7 이어서 n=7에서 for루프 벗어남. 해서 7의 지수 1에 대한 곱을 해줌
cnt *= 2;
}
return cnt;
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
| 014. Longest Collatz Sequence(짝수이면 n/2, 홀수는 3n+1인 변환에서 1이될 때까지 몇 번 변환인지 구하기) (4) | 2024.09.02 |
|---|---|
| 013. Large sum (50자리 정수에 대한 덧셈 구하기) (0) | 2024.09.02 |
| 011. Largest Product in a Grid (2차원 격자에서 가로/세로/대각선으로 수 읽고 최대곱 구하기) (0) | 2024.09.02 |
| 010. Summation of Primes (k보다 작은 모든 소수의 합 구하기) (0) | 2024.08.14 |
| 009. Special Pythagorean Triplet (합이 k가 되는 피타코라스 수 구하기) (0) | 2024.08.13 |