백준 알고리즘 7894번 : 큰 수

Zoo Da·2021년 7월 19일

백준 알고리즘 수학 재풀이예정!

백준 알고리즘

목록 보기

123/337

링크

(https://www.acmicpc.net/problem/7894)

문제

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

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

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 다음 줄부터 한 줄에 하나씩 정수 m이 주어진다. (1 ≤ m ≤ 107)

출력

입력으로 주어지는 수 m마다 m!의 길이를 출력한다.

예제 입력 및 출력

풀이법

... 고등학교 수학시간에 로그의 상용지표라는 것에 대해서 배웠을 것이다.
log10 = 1(밑이 10인 상용로그)
log100 = 2
log1000 = 3
...
이렇게 계속 하다보면 log12345678 = 7이라는 것을 알 수 있을 것이다.
문제에서 요구하는 것은 n!의 자릿수를 구하라는 문제인데 상용로그를 활용해서 문제를 풀 수 있다.
n!은 n(n-1)(n-2).....321이므로 양변에 로그를 취해서 나타내면

아래와 같이 쓸 수 있다(상용로그 공식에 의해 상용로그를 취했을 시 곱하기 연산은 더하기로 바뀐다.)
이걸 그대로 코드로 구현하면 된다.

풀이 코드(C++)

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm> 
#include <math.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) 
using namespace std;

int main(){
  fastio;
  int tc;
  cin >> tc;
  while(tc--){
    double s,result = 0;
    cin >> s;
    for(double i = 1; i <= s; i++){
      result += log10(i);
    }
    printf("%d\n",(int)result + 1);
  }
  return 0;
}