BOJ - 2777

백준 문제 링크
숫자 놀이

❓접근법

1. N의 약수와 관련된 문제이다.
   N의 약수를 구하기 위해 9 ~ 2 까지 차례대로 나누어서,
   나눠지면 N = N // i, div[i] += 1 해주고, 더 이상 안될 때까지 나눈다.
   • 예를 들어 N = 81의 경우 9로 나눌 수 있으므로
     N = 81 // 9 = 9, div[9] = 1
     N = 9 // 9 = 1, div[9] = 2
   2. 최종적으로 N이 1이되면 div의 합계를 출력한다.
   3. N이 1이 안되면 ( X가 없을 때 ) -1을 출력한다.
   4. 위 과정을 시작하기에 앞서 N = 1일 때는 N = 2로 바꿔주고 시작하면 된다.

N을 큰 수 부터 나누는 이유는,
N = 81 = 3 x 3 x 3 x 3, 이 경우 X = 3333
N = 81 = 9 x 9, 이 경우 X = 99
두 번째 경우가 더 작은 X가 되기 때문이다.

👌🏻코드

import sys
for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    
    if n == 1: n = 2
    div = [0] * 10
    
    for i in range(9, 1, -1):
        while n % i == 0:
            n = n//i
            div[i] += 1
            
    if n == 1:
        answer = sum(div)
        print(answer)
    else:
        print(-1)