[Python] BOJ 2231 분해합

총 걸린 시간 

1254 - 1310 (16min)

요구사항 

1. 시간 제한: 2초
2. 메모리 제한: 192MB
3. 자연수 N의 가장 작은 생성자를 구하라.

설계

1. 브루트 포스를 해야 된다 생각했다. 그 이유는 그 경우의 수 말고 방법이 안보인다. 
2. 해당 문제의 경우 생성자가 여러 개인 자연수도 있을 수 있고 없을 수 있다 했다. 하지만 이 두 가지 경우에 어떻게 출력해라 명시되어 있지 않으므로 임의로 가장 작은 생성자를 찾으면 프로그램을 종료하도록, 생성자를 찾지 못하면 0을 출력하도록 설계했다. 

 

구현

import sys

input = lambda: sys.stdin.readline().rstrip()

N = int(input())

# N의 가장 작은 생성자를 찾기 위한 브루트포스
for i in range(1, N + 1):
    # 각 숫자의 분해합을 계산
    sums = i + sum(int(digit) for digit in str(i))

    # 생성자를 찾으면 출력하고 종료
    if sums == N:
        print(i)
        exit()

# 생성자가 없으면 0 출력
print(0)

 

---

2025.12.03 재풀이 

N = int(input())
answer = 0

for i in range(1, N + 1 ): # 자연수임으로 1부터 시작. N을 포함해야하니 N + 1
    result = i 
    for digit in str(result):
        result += int(digit) # result == 분해합 
    if result == N: # i의 분해합의 결과가 N이라면 
        answer = i
        break

print(answer # 만약 if문에 걸리지 않았더라면 anwser == 0 을 출력할 것. 기존의 exit()은 코테에서 지양할 것

 

시간복잡도는 어떻게 될까?

위에서 시간 복잡도는 어떻게 될까? 

우선 첫 번째 for문은 O(N)의 시간복잡도를 갖는다. 

두 번째 for문은 O(logN)의 시간복잡도를 갖는다. 

그 이유는 한 자리의 시간복잡도는 9개

두자리의 시간복잡도는 10 ~ 99 90개

N = 10^k -1 

k = logN 

 

따라서 O(NlogN)의 시간복잡도를 갖는다. 

위 코드의 범위를 줄여보자. Hint 분해합은 너무 작은 수로는 될 수 없다. 

한 자리의 최대는 9

두 자리의 최대는 18 (99)

세 자리의 최대는 27 (999) 이다. 

 

N(분해합) = 256 이라고 해보자. 

M(생성자) + (각 자리의 합) = N 이다. 

 

각 자리의 합의 최대는 27이다. 

 

N(256) - 27 = 229 부터 생성자를 찾으면 된다. 

 

예를 들어.

200 + (2 + 0 + 0) = 202

217 + (2 + 1 + 7) = 237

 

위 처럼 너무 작은 수로는 분해합에 도달할 수 없다. 따라서 분해합에서 최대크기(여기선 27)을 뺀 수 부터 찾으면 된다. 

완성된 코드

N = int(input())
start = max(1, N - len(str(N)) * 9)
answer = 0

for i in range(start, N + 1):
    result = i
    for digit in str(i):
        result += int(digit)
    if result == N:
        answer = i
        break

print(answer)

 

결과