문제
n! = 1 × 2 × ... × n은 어떤 거듭제곱보다도 빠르게 커집니다. 25!만 해도 26자리입니다. n!을 정확히 계산한 다음 각 자리의 숫자를 더하세요. 큰 정수를 지원하지 않는 언어라면 수를 자릿수 배열로 저장하고 2, 3, ..., n을 차례로 곱하면 됩니다.
factorial_digit_sum(n) 함수를 구현하세요.
입력
n: 팩토리얼을 구할 수입니다.
출력
n!의 10진수 각 자리 숫자의 합을 반환합니다. 0! = 1이라는 점에 주의하세요.
제약 조건
0 ≤ n ≤ 1000
예시
예시 1
입력:
n = 5
예상 출력:
expected = 3
입력:
long long n = 5;
예상 출력:
long long expected = 3;
입력:
long n = 5;
예상 출력:
long expected = 3;
설명
5! = 120이고 1 + 2 + 0 = 3입니다.
예시 2
입력:
n = 0
예상 출력:
expected = 1
입력:
long long n = 0;
예상 출력:
long long expected = 1;
입력:
long n = 0;
예상 출력:
long expected = 1;
설명
0!은 정의에 따라 1이므로 답은 1입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
1에서 시작해 2, 3, ..., n을 차례로 곱하세요.
힌트 2
각 자리에 곱하고 받아올림을 더한 뒤, 일의 자리는 남기고 나머지는 받아올림으로 넘기세요.
힌트 3
마지막에 받아올림이 남아 있으면 새로운 자리가 됩니다.
예상 복잡도
시간 O(n × D) (D는 n!의 자릿수), 추가 공간 O(D)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.