Category
알고리즘  그리디

[2777] 숫자 놀이

by Hwang

문제

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

풀이

일의 자리수부터 가장 큰 숫자를 넣어주면서 N를 만드는 방식으로 풀이했습니다.

모든 자릿수의 곱이 가장 작으려면 낮은 자리수에 큰 수를 채워주면 됩니다. 따라서 가장 큰 숫자면서 N과 나누어 떨어지는 수를 dfs 방식으로 계속 곱해가며 값을 찾아주었습니다.

import sys

T = int(sys.stdin.readline())

def dfs(current, depth):
    global result
    if result != -1:
        return
    if current == 1:
        result = depth if depth != 0 else 1
        return
    for i in range(9, 1, -1):
        if current % i == 0 and result == -1:
            dfs(current // i, depth + 1)

for _ in range(T):
    N = int(sys.stdin.readline())
    result = -1
    dfs(N, 0)
    print(result)


 Comment