(Python) - BOJ(2777번) : 숫자 놀이

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

2777번: 숫자 놀이

---

• 해설 :

“양의 정수 N( 1 <= N <= 1,000,000,000 )이 있을 때 모든 자릿수의 곱이 정확히 N이 되는 가장 작은 양의 정수 X를 찾아라. ”

 

모든 자릿수의 곱이 20인 수들을 예를 들면, 522 보다는 225가 작고 225 보다는 45가 작다.

승환이는 자신이 만든 문제를 수업 시간 전에 칠판에 써 놓았다. 그것을 본 당신은 호기심이 생겨서 그 문제를 풀어보고 싶어한다. N이 주어졌을 때 위 조건을 만족하는 가장 작은 양의 정수 X가 몇 자리 수인지 구하여라.

 

 

 

---

• 풀이 :

N의 길이만큼 각 자릿수들을 곱하여 주어진 수를 만들 수 있는지 찾으면 된다. 

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    for _ in range(int(input())):
        N = int(input())
        answer = []
        flag = True
        if N == 1:
            print(N)
            continue
        while N != 1 and flag:
            flag = False
            for i in range(9,1,-1):
                if N % i == 0:
                    answer.append(i)
                    N = N // i
                    flag = True
                    break
        if flag:
            print(len(answer))
        else:
            print(-1)