백준 2331번 분해합 풀이 및 정답(python)

 

---

O(n) 풀이

해당 문제는 단순히 1부터 n까지 분해합을 찾으면서 답을 구해도 되는 문제입니다.

이렇게 하면 O(n)의 시간복잡도를 가지고 풀 수 있습니다.

하지만 막상 다른 사람들 제출한 시간을 보면 차이가 꽤 있을겁니다.

 

O(n) 풀이 + 분해합 특성 이용

하지만 분해합의 특성을 이용해서 시간을 줄일 수 있습니다.

분해합의 특성은 특정 자연수 n의 분해합은 n + (n의 자리수 * 9)까지라는 점입니다.

쉽게 999를 예시로 보면

999의 분해합은 999 + 9 + 9 + 9 라는 것이고

이 특성을 활용해서 분해합을 찾을 때 범위를 좁혀시작할 수 있습니다.

 

Python 정답코드

n = int(input())

answer = 0
start_value = max(1, n - (len(str(n)) * 9))

for i in range(start_value, n):
    j_list = list(map(int, str(i)))
    j_sum = sum(j_list)
    if n == (i + j_sum):
        answer = i
        break

print(answer)