020. Factorial Digit Sum (큰 수에 대한 팩토리얼 구하기)

​문제 (English)

$n!$ means $n \times (n-1) \times ... \times 3 \times 2 \times 1$.

For example, $10! = 10 \times 9 \times ... \times 3 \times 2 \times 1 = 3628800$,

and the sum of the digits in the number $10!$ is $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$.

 

Find the sum of the digits in the number $100!$.

 

Answer: 648

문제 분석

---

일반 변수로는 처리하지 못하는 큰 결괏값이 나오는 팩토리알 문제이다. $100!$ 값은 u64나 u128로도 처리하지 못한다. 

해서, 일반 초등학교때의 곱셈 방법과 동일하게, 각 자릿수를 배열로 정의하고, 루프를 돌며 곱셈을 하는 루틴을 만들라는 문제.

 

Java에서는 BigInteger를 이용해서, python에서는 math에 있는 factorial함수로 쉽게 큰 수에 대한 팩토리알을 할 수 있으나, 원래 의도한 이 문제는, 실제로 큰 수를 배열로 만들고, 이 큰 수에 대한 곱셈을 해보라는 것임.

 

풀이 1 

---

큰 수를 처리할 수 있게, 십진수의 각 자릿수를 담는 배열을 만들어서 수를 표현하고, 이 배열 수에 대해서 a를 곱한다면, 각 배열 자릿값마다 a를 곱해가며, 10보다 큰 값의 경우는 carry로 다음 자리로 넘기는 형태로, 곱셈 루틴을 만든다.

 

fn multiply(v:&mut Vec<usize>, a:usize) {    
    let mut carry = 0;
    for i in 0..v.len() {
        let val = carry + v[i] * a;
        
        v[i] = val % 10;
        carry = val / 10;
    }
    while carry > 0 {
        v.push(carry % 10);
        carry /= 10;
    }    
}

 

고정된 길이가 아니고, carry가 생길 때마다 v.push()에 의해 벡터의 크기를 늘려나간 것에 유의.

 

팩토리알이기에 n 이하의 수를 모두 곱해나가야하기에 for 루프로 i값을 n까지 증가시키면서, 위의 multiply 함수를 호출하면 되겠다.

fn answer(n:usize) -> usize{
    let mut v:Vec<usize> = Vec::new();
    v.push(1);

    for i in 2..=n {
        multiply(&mut v, i);
    }
    return v.into_iter().sum();
}

 

 

총평

---

큰 수를 배열형태로 표현하고, 이 배열에 대해 곱셈을하건 덧셈을 하건 어떤 연산을 할 때의 기본 루틴은 다음과 같다. 이러한 형태의 루틴은 많은 알고리즘에서 사용되는 전형적인 루틴이기에, 잘 기억해 둘 필요가 있다.

1)해당 자리의 값과 연산을 하고, 이전 자리에서 넘어온 carry와 더한다.   val = v[i] * a + carry

2)10을 모듈레이션해서 그 값을 해당 자리에 넣는다. v[i] = val % 10

      이때 동일한 배열을 재활용해도되고, 새로운 결괏값을 저장하는 v2 같은 배열을 사용해도 된다.

3)10보단 큰 부분은 carry로 넘긴다.   carry = val / 10

4)해당 배열의 끝까지 위 1~3을 반복한다.

5)위 루프를 벗어났을 때, carry가 남아 있으면, 이 carry를 결괏값 배열에 push 한다.

 

코드로 나타내면, 

for i in 0..v.len() {
    let val = carry + v[i] * a;

    v[i] = val % 10;
    carry = val / 10;
}
while carry > 0 {
    v.push(carry % 10);
    carry /= 10;
}

 

전체 소스코드

---

p20.rs 

#[test]
fn test(){
    assert_eq!(27, answer(10));
    assert_eq!(648, answer(100));
}

#[cfg(test)]
fn answer(n:usize) -> usize{
    let mut v:Vec<usize> = Vec::new();
    v.push(1);

    for i in 2..=n {
        multiply(&mut v, i);
    }
    return v.into_iter().sum();
}

#[cfg(test)]
fn multiply(v:&mut Vec<usize>, a:usize) {    
    let mut carry = 0;
    for i in 0..v.len() {
        let val = carry + v[i] * a;
        
        v[i] = val % 10;
        carry = val / 10;
    }
    while carry > 0 {
        v.push(carry % 10);
        carry /= 10;
    }    
}

 

끝