(백준, 파이썬) 분해합

---

2231 - 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

---

-맞힌 코드-

#메모이제이션 이용
#인덱스(해당숫자)에 대한 분해합 입력
#입력 받은 N값을 갖는 생성자(인덱스) 리스트 찾기.
#min값 출력
 
N = int(input())
memo = [1] * 1000001
 
for i in range(1, len(memo)):
    decomposed_sum = i
    for s in str(i):
        decomposed_sum += int(s)
    memo[i] = decomposed_sum
 
find_lst = list(filter(lambda x : memo[x] == N, range(len(memo))))
 
if len(find_lst) == 0:
    print(0)
 
else:
    print(min(find_lst)) 

 

풀고나서 좀 싸했다(푸는 내내 무거운 느낌이었음)

이렇게 안 풀어도 빠르고 간결한 풀이가 있을 것 같은데?

---

다른 풀이를 찾아보니 PyPy를 이용하면 시간이 꽤나 많이 줄어드는 듯 하다.

그래도 코테는 PyPy로 보는게 아닐테니 꼭 써야하는 문제 아니면 시간초과를 줄이는 연습을 해야겠지?

 

대부분 1500~2000ms 정도 걸린 것 같다. (나는 2024ms)

그러다가 1164ms 짜리 Python 풀이를 발견했다.

---

-다른 분의 풀이-

import sys
n = int(sys.stdin.readline())
sum = 0
if n>1:
    for i in range(1,n):
        j=i #j 선언 - 자리수 더하려고
        while(True):
            if j//10>0: #십의 자리수를 넘어가는 자리들에 대해서
                sum+=j%10#그 자릿수만 더해준다
                j=j//10#한칸씩 땡겨준다
            else:
                sum+=j  #마지막으로 일의자리를 더해준다
                break
        sum+=i  #원래 수를 더해준다
        if sum==n:  #만약 n과 i의 분해합과 동일하다면
            print(i)  #i를 프린트한다(순차적으로 들어가므로 i가 제일 빠름)
            break
        else:
            sum = 0 
            #n값을 갖는 i의 분해합이 없다면 분해합은 0이다
if sum==0 or n==1:  
    #1의 경우와 위 else문의 경우에는 생성자가 없으므로 0을 출력한다.
    print(0)

입력받은 N에 한해서 N과 분해합이 같아지는 i를 찾는 코드인 것 같다.

보면서 뭔가 가독성이나 표현자체를 예쁘게 할 수 있지 않을까 해서 한번 만져봤다.

N = int(input())
 
for i in range(1, N):
    jari = i
    decomposed_sum = 0
        
    for s in str(jari):
        decomposed_sum += int(s)
    decomposed_sum += i
        
    if decomposed_sum == N:
        min_maker = i
        break
    
if decomposed_sum == N:
    print(min_maker)
        
else:
    print(0)

이름 바꾸고.. int로 만진게 아니라 str 이용해서 더한 정도가 끝인 듯?

---

어쩌면 모든 분해합을 갖고 있다가 그때그때 뽑을 수 있는 내 코드가 더 나을지도?

(길이도 짧을지도?)