[백준/Python] 2231번 분해합 문제

■ 2231번 분해합 문제

 

출처: 백준 2231번 분해합 문제

 

■ 코드 풀이

 

아이디어를 설명해 드리겠습니다. 입력받은 자연수 N은 분해합입니다. 자신과 각 자릿수의 합입니다. 자연수 N의 가장 작은 생성자를 구하기 위해서는 먼저 각 자릿수의 합의 최댓값을 빼주고 시작합니다. 자연수 N의 최댓값은 백만이므로 나올 수 있는 자릿수의 합의 최댓값은 54(N이 999,999일 경우)입니다. 이때 입력받은 값이 54보다 작을 경우 음수가 나오므로 if 조건으로 구분해 줍니다.

이제 N-54부터 N까지 1씩 증가시키면서 total이라는 변수에 자기 자신과 각 자릿수의 합을 더해 새로운 분해합을 만듭니다. 그리고 이 분해합이 최초 입력받은 수 N과 같아지는 순간 break로 for문을 탈출하면 total에 있는 숫자가 바로 최소 생성자가 됩니다.

 

N = int(input())
end = False

if N >= 55: # N이 55 이상인 경우
    for i in range(N-54, N):
        total = i
        for j in range(len(str(i))):
            total += int(str(i)[j])

        if total == N:
            print(i)
            end = True
            break
        
else: # N이 1 이상 54 이하인 경우
    for i in range(0, N):
        total = i
        for j in range(len(str(i))):
            total += int(str(i)[j])

        if total == N:
            print(i)
            end = True
            break
            
if end == False:
    print(0)