반응형
문제 (English)
$2^{15} = 32768$ and the sum of its digits is $3+2+7+6+8=26$.
What is the sum of the digits of the number of $2^{1000}$?
Answer: 1366
문제 분석
$2^{1000}$을 십진수로 나타내면 자릿수가 302자리로 일반적인 변수 u64, u128로는 계산이 안된다.
$ 1 + 1000 \times Log_{10}{2} = 302 $
각 자리를 배열로 나타내고, 그 배열값에 대해 2를 곱하는 형태로 하면, 302 자릿수에 대해서도 계산이 되겠다.
풀이 1
$2^{15}$에 대해 생각해보자. 자릿수는 $1+15\times log{2}=5$
5자리의 배열을 만들고, arr[0]=1에서 출발해서 2를 곱해 나가자.
만약 곱한 값이 10 미만이면 그대로 곱한 값을 쓰고, 10 이상이면 carry 1을 넘겨주는 형태로.
fn answer(n:usize) -> usize {
//1. calculate ditits. if n=15, 2^15=32768. digits = 1 + 15*Log2 = 5
let digits = 1 + (n as f32 * std::f32::consts::LOG10_2) as usize;
//2. make arry with digits length
let mut narr:Vec<usize> = vec![0; digits];
narr[0] = 1;
//3. loop with multiply 2
let mut order:usize = 0;
for _ in 0..n {
let mut carry:usize = 0;
let mut j:usize = 0;
while j <= order {
let p = narr[j] * 2 + carry;
narr[j] = p % 10;
carry = p / 10;
//if carry exist then encrese order
if j == order && carry > 0 {
order += 1;
}
j += 1;
}
}
return narr.into_iter().sum();
}
이 코드로 hackerrank도 통과할 수 있다.
총평
아주 큰 수에 대한 곱셈을, 배열로 만들어서 처리할 수 있느냐를 물어보는 문제.
큰 수와 큰 수간의 곱셈을 처리하는 것은 꽤 복잡하나, 큰 수에 2를 곱하는 것은 비교적 쉽게 구현이 가능하다.
전체 소스코드
p16.rs
//알고리즘 구상
//- 2^1000은 1+1000Log(2)=302자리 수. 따라서, u128로도 처리할 수 없음
//- 302자리 수에 대해, 처음 1부터 시작해서 2씩 곱해나가면, 4,8,16...이 되고, 1000번 곱하면 2^1000이 된다.
//- 즉, 배열처럼 된 십진수 값에 대한 곱셈 연산을 짜게하는 문제
// 1: 0001 * 2 = 0002
// 2: 0002 * 2 = 0004
// 3: 0004 * 2 = 0008
// 4: 0008 * 2 = 0016
// 5: 0016 * 2 = 0032
// 6: 0032 * 2 = 0064
#[test]
fn test(){
assert_eq!(26, answer(15)); //2^15=32768, 3+2+7+6+8=26
assert_eq!(1366, answer(1000));
}
#[cfg(test)]
fn answer(n:usize) -> usize {
//1. calculate ditits. if n=15, 2^15=32768. digits = 1 + 15*Log2 = 5
let digits = 1 + (n as f32 * std::f32::consts::LOG10_2) as usize;
//2. make arry with digits length
let mut narr:Vec<usize> = vec![0; digits];
narr[0] = 1;
//3. loop with multiply 2
let mut order:usize = 0;
for _ in 0..n {
let mut carry:usize = 0;
let mut j:usize = 0;
while j <= order {
let p = narr[j] * 2 + carry;
narr[j] = p % 10;
carry = p / 10;
//if carry exist then encrese order
if j == order && carry > 0 {
order += 1;
}
j += 1;
}
}
return narr.into_iter().sum();
}
끝
반응형
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
018. Maximum Path Sum I (삼각형 모양의 수 집단에서, 최대합이 되는 경로 찾기) (1) | 2024.09.02 |
---|---|
017. Number Letter Counts (숫자를 영어로 읽었을 때, 몇 개의 문자가 되는지 구하기) (5) | 2024.09.02 |
015. Lattice Paths (격자에서 원점에서 마지막점까지의 경로에 대한 경우의 수 구하기) (2) | 2024.09.02 |
014. Longest Collatz Sequence(짝수이면 n/2, 홀수는 3n+1인 변환에서 1이될 때까지 몇 번 변환인지 구하기) (4) | 2024.09.02 |
013. Large sum (50자리 정수에 대한 덧셈 구하기) (0) | 2024.09.02 |