[백준 2331번-파이썬/Python] 분해합

http://acmicpc.net/problem/2331

{코드}

def func():
	n = int(input())
	m = max(n - 9*len(str(n)),0)
	for i in range(m, n):
		if n == sum(map(int, str(i)))+i:
			return i
	return 0
print(func())

{설명}

각 자릿수의 합을 구하기 위해 문자열의 각 인덱스마다 정수로 변환해서 그 합을 구한다.

거기에 기존의 수를 더한 결과가 타겟 수와 같으면 생성자 수이므로 이를 반환한다.

만약 반복문이 끝날 때까지 생성자를 찾지 못하면 0을 반환한다.

그리고 어떤 수에 대해서 생성자가 될 수 있는 최솟값은 n에서 9*(자릿수의 개수)를 뺀 값인데 0 이상이어야 하므로 0과 비교하여 더 큰 값부터 시작하게 됩니다.

이 코드가 있음으로서 코드의 실행속도는 일반적인 브루트포스 방식보다 몇십배는 빠르게 작동합니다. (보통 1000ms이상 걸리던데 이 코드는 68정도가 나오더라고요)