[백준/파이썬] 2231: 분해합

https://www.acmicpc.net/problem/2231

 

문제 요약 : 자연수 N의 분해합이 주어질 때, N의 가장 작은 생성자를 찾아라

M+ M의 각 자리수의 합 = N  -> M을 N의 생성자라고 함

예를들어 245의 분해합은 256(= 245 + 2 + 4 + 5) 이므로 245는 256의 생성자

 

 

예제 입력1 :

216

 

예제 출력 1:

198

 

📌 풀이 )

1부터 N까지 반복하면서 각 숫자 i에 대해 분해합을 계산한다.

분해합과 i(원래 숫자)를 더하여 N과 같으면 i를 반환한다.

모든 숫자를 검사해도 생성자가 존재하지 않으면 0을 반환한다.

 

이 코드는 1부터 N까지 모든 수를 검사하기때문에 최악의 경우 시간복잡도는 O(N)이다. N의 최대값이 1000,000이므로 가능한 코드이다.

def result(N):
    for i in range(1, N + 1):
        digit_sum = sum(map(int, str(i)))
        if i + digit_sum == N:
            return i
    return 0

N = int(input())
print(result(N))