알고리즘 - 백준 - 브루트포스 - 2231 - 분해합(파이썬)

알고리즘 - 백준 - 브루트포스 - 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을 출력한다.

 

코드

import sys

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

for i in range(1,N+1): #1부터 입력받은 N까지 출력하기 위해 N+1을 해줌

    num = list(str(i)) #숫자의 각 자릿수가 리스트로 저장 256이면 [2,5,6]으로 저장
    
    for k in range(len(num)):  #리스트에 string으로 저장했으므로 int로 변환
        num[k] = int(num[k])
        
        
        
    if i+sum(num) == N: #i와 i의 각 자리수값 더한것이 입력받은 N과 같으면 끝
        print(i)
        break
        
        
    if i==N: #끝까지 돌았는데도 못찾으면 생성자가 없어서 0
        print(0)

 

코드설명

분해합은 어떤 수 N의 N과 N의 각 자리수의 합

245는 245 + 2 + 4 + 5 -> 256

245는 256의 생성자

256은 245의 분해합

 

문제 -> N의 가장 작은 생성자는??

N은 어떤수 + 어떤수의 각 자리수

 

1)sys.stdin.readline으로 N을 입력받는다.

2)1부터 N+1까지 돌면서 숫자의 각 자리수는 리스트로 저장한다 -> 52면 ['5','2']

3) 단 string으로 저장 후 다시 int로 변환해준다

4) i와 i의 각 자리수값(리스트) 더한것이 입력받은 N과 같으면 끝

5) 없으면 0 출력(생성자가 없음)

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main