[BOJ]2231번 분해합

1. problem : 

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

 

 

 

2. solution 1 : 

#%%
int_num = int(input()) # 216을 input으로 넣는다고 가정
init_num = -1
for i in range(0,int_num):
    str_num = str(i)
    sol1_sum = i 
    for j in str_num:
        sol1_sum += int(j) 
    if sol1_sum == int_num:
        init_num = i
        break 
print(init_num)

그냥 0부터 input num까지 brute force를 적용하고 있다. 

 

3. solution 2 : 

N = int(input())  # 예: 216
ans = 0

# 생성자는 N보다 작거나 같은 숫자이므로, 그 범위로 반복
for i in range(max(0, N - len(str(N)) * 9), N):
    # i의 각 자릿수의 합을 계산하여 i에 더함
    digit_sum = sum(map(int, str(i)))
    if digit_sum + i == N:
        ans = i
        break

print(ans)

이 방법은 참신하다. input_number에-자릿수*9를 계산하여, 범위를 좁힌다. 왜냐하면, 생성자를 만들기 위해서는 기존 넘버 + 각자리 넘버합인데 각자리의 최댓값은 9다. 따라서 각자리의 최댓값을 자릿수로 곱하면 더할 수 있는 최댓값이 된다. 이때, 이 값을 뺀 값에서부터 시작할 수 있어 상당히 효율적이다. 하지만 , input_number가 11이라고 하면, 11-9*2 하면 -7이 된다. 이때는 오히려 -값이 나와 방해가 된다. 따라서, max 함수를 써서, 0과 경쟁한다.