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

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

7894번: 큰 수

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main()
{
   int T;
   cin >> T;

   while(T--)
   {
      double m, result = 0;
      cin >> m;
      for(double i=1; i<=m; i++)
      {
         result += log10(i);  //상용로그
      }
      cout << int(result) + 1 << "\n";
   }
}

원래 팩토리얼을 따로 구하기 이를 문자열로 변환하여 길이를 구해서 풀었는데 계속 틀렸다.

다른 방법이 떠오르지 않아서 검색했더니 상용로그를 활용한 문제였다.

 

log10(10) = 1, log10(100)2 인 성질을 이용한다.

따라서 팩토리얼의 값이 만약 3628800이라면 log10(3628800)은 약 6.6이 나오게된다.

규칙을 보면 log10(해당 값) 은 해당 값 - 1만큼의 길이를 가진다.

 

log10(n!) = log10(n) + log10(n-1) .... log10(2) + log10(1)이다.

따라서 각 값마다 상용로그를 씌워서 길이를 구하고 마지막에 1을 더해준다.

 

검색하지 않았다면 아마 어지간해선 못풀었을 것 같다.