[알고리즘/백준] 2777번 숫자 놀이 Python 파이썬

 

한동안 취직 관련 과제 전형하느라 좀 쉬다가 다시 공부시작하네요.

이번 문제는 꼬아놓은 부분이 있어서 생각을 해야하는 문제였습니다. 

 

 

해당 문제 풀면서 중요하게 봐야하는 점은

1. 각 자릿수를 곱하면 정수 N 이 되어야한다는 것 

2. 가장 작은 정수 X가 몇 자리 수인지 출력해야한다는 점입니다.

 

각 자릿수를 곱한다는 이야기는 한 자리 숫자라는 것을 의미합니다 고로 2~9 사이 숫자로 구성되어야합니다. 11이나 13 이런 숫자는 안된다는 것을 의미합니다. 

 

가장 작은 정수의 몇 자리 수인가 이는 한자리 최대값을 찾아줘야합니다. 결국 생각해보면 22225 라고 할때 85로 바꿔줘야한다는 소리입니다. 33이면 9로 바꾸듯이! 그래서 2~9 사이 나눠지는 값을 찾을때 2부터 순서대로 찾는 것이 아닌 9부터 찾게 되면 자동스럽게 나눠지는 제일 큰 수를 찾아주게 됩니다. 

 

그 이후에는 나눠진 숫자들의 갯수를 생각하면 자릿수를 구할 수 있습니다.

 

다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

# 큰 거부터 찾아야 정답내기 쉽기 때문에
test_check = [i for i in range(9,1,-1)] 
T = int(input())
for i in range(T):
    n = int(input())
    nums = []
    final_check = 0
    if n == 1: # 처음에 1값 들어올 경우 대비 예외처리
        nums.append(1)
    else:
        while True:
            check = 0 # 2~9까지 나눠지는 숫자인지 아닌지
            for j in test_check:
                if n%j == 0:
                    nums.append(j)
                    n = n//j
                    check = 1
                    break
            if n == 1: # 다 나눴을 경우
                break
            if check == 0 and n > 10: # 안 나눠지는데 10이상이면 10이상 소수라는 이야기
                final_check = -1
                break
    if final_check == -1:
        print(final_check)
    else:
        print(len(nums))

 

처음에는 2부터 나눠서 찾을려고 생각하니 나중에 최댓값은 어떻게 찾아주지.... 머리가 엄청 복잡해졌는데 이렇게 거꾸로 계산하는 것만으로도 쉽게 풀리는 문제가 있다는 것을 깨닫는 문제였습니다. 그리고 1을 입력 받을 때의 예외처리도 잊지 말아야합니다.