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

문제 설명

풀이 전략

주어진 입력인 분해합에서 역으로 생성자를 추정하는 것은 어려운 일이다. 생성자가 여러 개일 때는 가장 작은 수를 출력해야하므로 작은 수부터 키워가며 분해합을 생성해 본다. 효율적인 계산을 위하여 자릿수에 따른 최소 숫자부터 시작하는 것이 좋다. 각 자릿수를 더할 때에 두 가지 방법으로 구현하였다.

1. 몫과 나머지를 이용한 자릿수
2. 파이썬의 문자열 to 정수 변환

실행 시간에 큰 차이는 나지 않아 어떤 방법을 사용해도 상관없어 보인다. 2의 방법에서는 int()를 이용한 변환에서 인자가 음수일 경우에는 ValueError가 발생하여 음수 여부를 체크하여 생성자 체크 시작 지점을 설정했다.

코드

1. 몫과 나머지를 이용한 자릿수

n = int(input())
count = len(str(n))
for num in range(n - count*9 ,n+1):
    temp = num_sep = num
    for k in range(1,count+1):
        a = 10**(count-k)
        num_sep += temp // a
        temp -= (temp // a) * a
    if num_sep == n:
        break
if num == n:
    print(0)
else:
    print(num)

2. 파이썬의 문자열 to 정수 변환

n_str = input()
n = int(n_str)
flag = False

if n - len(n_str)*9 > 0:
    checkstart = n - len(n_str)*9
else:
    checkstart = 0

for num in range(checkstart ,n+1):
    test_num = num
    for c in str(num):
        test_num += int(c)
    if test_num == n:
        flag = True
        break
if flag:
    print(num)
else:
    print(0)