<브루트 포스> 2231번 분해합 with 파이썬

 

문제

 어떤 자연수 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을 출력한다.

정답비율

48.119%

 

# 분해합 구하기
def deSum(n) :
    numstr = str(n)
    s = n
    for i in range(len(numstr)) :
        s = s + int(numstr[i])
    return s

# 생성자 찾기
def findCon(m) :
    for i in range(m) :
        if m == deSum(i) :
            return i
    return 0

N = int(input())
print(findCon(N))

 

 문제를 간단하게 해석해보면, 자연수를 쪼개서 더하고 원래 자연수를 더한것이 분해합이다. 문제에서 요구하는 것은 숫자가 주어지면 그 숫자를 분해합으로 만들어내는 자연수를 찾으라는 것이다.

 

 하나의 함수로 해결하려 했으나 for문이 두 개나 들어갈 뿐더러 하나의 함수에 두 가지의 기능을 넣는 것은 그다지 좋지않으므로 나누었다. 먼저 분해합을 구하는 함수를 deSum으로 만들었다. 숫자를 문자열로 변환하고 각 자리에 있는 숫자들을 주어진 숫자에 모두 더하고 return한다.

 

 생성자를 찾는 함수는 숫자가 주어지면 그 이하의 모든 자연수를 for문으로 돌며 분해합합수에 넣어가며 찾도록 하였다.

 

 

---

 

 

참고

 

2231번: 분해합