[BOJ] 2231. 분해합

문제

---

216이라는 수가 주어졌을 때 216 = 198 + 1 + 9 + 8 을 만족하는 198이라는 수를 찾는 문제이다.

포인트

---

효율성에 대한 제한이 없어 1 부터 찾아도 되지만, x라는 수가 주어졌을 때 답이 abc 라면 x = abc + a + b + c 이다. 이때 a, b, c < 9 이므로 x - 27 부터 찾아나갔다. 또한 각 자릿수를 합한 값과 x 의 차이의 반 만큼 증가시켰다.

이때 36 같은 경우는 29는 합이 40이므로 예외가 발생한다. 또한 dif = 1 이면 무한루프에 빠지게 된다.

코드

---

str1 = input()
n = int(str1)

a = n - 9 * len(str1)
if a < 0:
    a = 1


def cal(a):
    a1 = a
    a1 += sum(map(int, str(a)))
    return a1


dif = n - cal(a)
while dif != 0 and a <= n:
    if dif <= 1:
        dif = 2
    a += dif >> 1
    a1 = cal(a)
    dif = n - a1

if dif == 0:
    print(a)
else:
    print(0)