백준 2231번 - 분해합 : 브루트 포스 알고리즘

 

2231번: 분해합

 

나의 풀이:

216보다 작은 수 부터 시작해서 분해합을 구하고 그 합이 216과 같은지 확인하는 방법을 선택했다.

브루트 포스 알고리즘이다보니 모든 경우를 조사하기 때문에 이 방법을 선택했다.

하지만 어느 정도 숫자에 도달하면 216이 될 수 없기 때문에 (예를 들어 215,,200 천천히 분해합을 보다 100이나 더 작은수까지 가면)일일이 분해합을 끝까지 1이 될 때까지 구하면 효율성이 떨어진다.

입력값의 생성자의 최소를 가늠해서 반복문을 break해야 시간복잡도가 좀 더 좋아질 것이다. 나는 적어도 n // 2 값까지 검사하면 충분한 범위에서 생성자를 찾을 수 있을 거라 생각했다.

코드

def cal(x):
    sum = x
    while x > 0:
        sum += x % 10
        x = x // 10
    return sum

if __name__ == "__main__":
    n = int(input())
    temp = n
    ans = 0
    while True:
        temp -= 1
        res = cal(temp)
        if res == n:
            ans = temp
        elif temp < n // 2:
            break
    print(ans)