탐욕적으로 생각하기 연습 -소인수분해 말고 인수분해하기-

1. 문제

 

2777번: 숫자 놀이 (acmicpc.net)

2777번: 숫자 놀이

 

각 자리수의 곱이 n이 되는 가장 작은 자리수의 개수를 가지는 정수를 찾는 문제

 

 

2. 풀이

 

정수 n은 소수들의 곱으로 소인수분해 할 수 있으니까,

 

n의 소인수분해를 찾는데 소인수가 10을 넘어가면 불가능하다.

 

따라서 가능한 소인수는 2,3,5,7의 곱으로 이루어져야 한다.

 

그러면 이 곱을 쭉 나열해서 얻은 정수가 조건을 만족하는 정수가 될것이다

 

예를 들어 곱이 20인 정수는 225 522 252... 등이 있다.

 

그런데 이 소인수들을 압축시켜야 가장 작은 정수가 될 것이다

 

즉 2*2 = 4니까 45가 되어야 가장 작은 자리수의 개수를 가지는 정수가 될 것

 

그래서 이렇게 소인수분해하고, 압축시키는 과정을 할려고 하니까.. 계속 틀리는거

 

from sys import stdin

T = int(stdin.readline())

for _ in range(1,T+1):
    
    n = int(stdin.readline())

    if n == 1:
        
        print(1)
        continue

    prime = {2:0,3:0,5:0,7:0}

    p = 2

    no = False

    while p*p <= n:
        
        if p > 7:
            
            no = True
            break
        
        if n % p == 0:
            
            while n % p == 0:
            
                n = n//p
                prime[p] += 1
        p += 1
    
    if no:
        
        print(-1)
    
    else:

        if n > 1:
            
            if n > 7:
                
                print(-1)
                continue
            
            else:
                
                prime[n] += 1

        a,b = divmod(prime[2],3)

        if b == 2:
            
            b = 1
        
        elif a == 2 and b == 0:
            
            a = 1

        c,d = divmod(prime[3],2)

        answer = a+b+c+d+prime[5]+prime[7]

        print(answer)

 

2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고

 

3의 경우 2번 곱한 9까지 압축시켜야하고

 

5,7은 그대로 두면 되고

 

근데 또 압축이 가능한 경우가 2*3=6으로도 압축이 가능하더라고??

 

그래서 고려해야할 부분이 너무 많아져서 지저분해지더라

 

애초에 맞지도 않고

 

----------------------------------------------------------------------------------------------------------------------

 

조금 더 탐욕적으로 생각하면

 

결국에 어떤 정수 n을 정수들의 곱으로 분해할건데, 꼭 소인수분해를 해야하냐 이거지

 

소인수분해를 한 다음에 이들을 곱해서 자리수를 줄여나가는 것이 비효율적이다

 

그냥 처음부터 n을 9부터 2까지 나눠보는거다

 

n을 9로 나누어 떨어지지 않을때까지 계속 나눠보는거다.

 

어느 순간 나누어 떨어지지 않으면, 8로 나누어보고..

 

그러다가 나누어 떨어지지 않으면, 7로 나누어보고..

 

그래서 n에 대한 2~9까지 지수를 구하면, 그것이 최소의 자리수 개수를 가지는 인수들의 곱이 될거다.

 

from sys import stdin

T = int(stdin.readline())

for _ in range(1,T+1):
    
    n = int(stdin.readline())

    if n == 1:
        
        print(1)
        continue

    answer = 0

    for d in range(9,1,-1):
        
        while n % d == 0:
            
            n //= d
            answer += 1
    
    if n >= 10:
        
        answer = -1
    
    print(answer)

 

n이 1인 경우는 예외처리해서 1 출력하고 continue해주고

 

n이 2 이상부터는 9부터 2까지 나누어 떨어지지 않을때까지 나눠보면서, 지수를 카운트해준다

 

그냥 그것들을 그대로 나열하면 그것이 최소 자리수 개수를 가지는 정수니까

 

예를 들어 곱이 20이 되는 정수는...

 

9부터 시작해서 나눠볼때...

 

5에서 나누어 떨어지니까  20 > 4

 

4는 5로 나누어 떨어지지 않아서..

 

다시 4는 4로 나누어 떨어지니까...

 

20 = 5 * 4가 될거고

 

4와 5를 그대로 나열한 45나 54가 최소 자리수 개수를 가지는 정수가 된다

 

그리고 계속 나눠봤는데, 남은 정수 n이 10 이상이 된다면, 두자리수 인수를 가지니까, 조건에 맞지 않아서 -1 출력