[백준] 7894 큰 수 (C++)

작성일 Edited on In , Views: Disqus:

문제

원문 링크 : https://www.acmicpc.net/problem/7894

많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다.

수가 주어지면, 그 수의 팩토리얼의 자리수를 구하는 프로그램을 작성하시오.

풀이 및 구현

주어진 정수 $m$의 범위가 $(1 \leq m \leq 10^7)$ 이므로 그대로 $m!$을 구하기엔 무리가 있다.

그래서 사용한 것이 로그이다.

$\log(a)$는 $a$를 만들기 위한 10의 지수 값을 물어보는 것인데, 이때 지수 값은 곧 자리수와 연관이 있다.

100으로 예를 들어보면 $\log(100) = 2$이고 100의 자리수는 총 3자리이다.

또한 954도 계산해보면 $\log(954) = 2.9795…$이고 954의 자리수는 총 3자리이다.

즉 계산한 결과에 로그를 취해서 소수점을 절사한다음 1을 더해주면 자리수가 나오는 것이다.

$$m! = m * (m - 1) * (m - 2) * … * 2 * 1$$

위 식에 로그를 취하면 로그의 성질에 의해 곱셈이 덧셈으로 분리된다. 따라서 아래와 같은 식으로 변한다.

$$\log(m!) = \log(m) + \log(m - 1) + \log(m - 2) + … + log(2) + log(1)$$

자리수는 1~m까지의 각각의 로그값의 합의 소숫점을 절사한 뒤 1을 더해주면 얻을 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        
        double count = 0;
        for (int i = 2; i <= N; i++) {
            count += log10(i);
        }
        count += 1;
        cout << (int)count << '\n';
    }
}

후기


오차때매 틀릴 것 같아서 걱정했었는데 다행히 AC를 받을 수 있었다.