[BOJ] 2231 분해합(Python)

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

2231번: 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력 1

216

예제 출력 1

198

해설

분해합을 처음 봤을때, 이거 관련된 수학 공식이나 이론이 있을까? 라는 생각을 했다. 하지만 내 머릿속에는 당연하게 그런 정보가 없었고 숫자를 하나씩 돌면서 분해합의 생성자를 찾는, 즉 브루트 포스(단순 무식)법으로 해결해야겠다고 생각했다.

 

그런데 진짜 무식하게 1~N까지 모두 돌면서 생성자를 찾는 것은 너무 비효율적일 것이라는 생각이 들었다.

위의 예시대로 본다면 

256(=245+2+4+5)의 생성자는 245 

생성자를 모른다고 가정 했을 때, 256은  (256 - 9 -9 -9) 사이에 있을 것이다. 

분해합 = 생성자 + 생성자의 일의 자리 수 + 생성자의 십의 자리수 .....

생성자에서 더하는 부분을 이항시켜보자 

생성자 = 분해합 - 생성자의 일의 자리 수 - 생성자의 십의 자리수 .....

각 자리수의 최대값이 9이고 생성자가 몇 자리수인지는 모르나 최소 분해합과 같거나 한 자릿수 낮을테니 그냥 분해합의 자릿수라고 가정한다면,

생성자 > 분해합 - 분해합 자릿수 X 9 

임을 알 수 있다. 

그렇다면 1부터 숫자를 순회할 필요는 없으므로 좀 더 효율적이다.

전체 코드

a =input()
b = 9*(len(a)) #분해합의 자릿수 * 9
k = int(a)
for i in range(k-b,k):
    c = str(i) #각 자릿수의 숫자를 꺼내오기 위해서 string으로 형변환 한다.
    d = i  # d를 검사하는 숫자로 할당
    for e in c:
        if e == '-': # 분해합의 숫자가 9보다 작으면 음수가 나올 수 있다.
            pass
        else:
            d += int(e) # 미리 검사하는 숫자로 할당한 d에서 각 자릿수를 또 더해준다.  
    if d == int(a):
        print(i)
        break
else:
    print(0) #break로 나오면 실행하지 않는다.

순회하는 숫자가 음수가 나올 경우도 고려하고 for문을 통해 검사하면서 생성자를 찾으면 break를 걸어버린다.

for.. else 구문은 무엇이냐면,

for에서 break가 걸리면 else 블럭의 코드는 실행시키지 않는다.

그래서 생성자가 없을 때의 경우를 고려해서 사용했다.