백준 2777 - 숫자 놀이

https://www.acmicpc.net/problem/2777

관찰

모든 자릿수의 곱이 N이 되어야 한다. 다시 말하면 N을 만들기 위해 10보다 작은 양의 정수로만 구성되어야 한다.

 

그리고 N을 만드는 가장 작은 양의 정수 X의 자릿수가 몇개인지 출력하라고 했지 실제 값에는 관심이 없다.

 

만약 1로만 나눈다고 하면 X는 111111.... 이렇게 무한한 수가 나올 것이다. 즉, 우리는 가장 작은 X를 만들기 위해 가능한 큰 숫자로 나누는 것이 좋음을 발견할 수 있다.

풀이

N을 만드는 가장 작은 X의 자릿수를 구하려면 어떻게 할까? 가장 큰 숫자로 나누는게 좋음을 알았으니 우리가 할 일은 9부터 2까지 반복문을 돌면서 최대한 N을 나누는 것이다. 1은 위처럼 1111... 의 형태가 나와 영원히 끝나지 않게 되므로 제외한다.

 

나머지가 생기면 다음 숫자로 넘어가고 N이 10 미만으로 작아지면 그대로 반복문을 탈출하면 된다.

 

이렇게 나눌 수 있을만큼 나눴을 때 최종 N이 10 미만이면 나눈 횟수가 정답이 된다.

 

10 이상이면 N을 만드는 X가 없다는 뜻이므로 -1을 출력하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int t;
 
void solve()
{
  cin >> t;
 
  while (t--)
  {
    int n;
    cin >> n;
    int ans = 0;
    
    if (n < 10)
    {
      cout << 1 << '\n';
      continue;
    }
    
    for (int i = 9; i >= 2; i--)
    {
      while (n % i == 0)
      {
        ++ans;
        n /= i;
      }
 
      if (n == 1) break;
    }
 
    cout << (n == 1 ? ans : -1) << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록