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

2231번: 분해합

---

def digit_sum(n):
  sum = n
  while n > 0:
    sum += n % 10
    n //= 10
  return sum

n = int(input())

digit = len(str(n))
front = n // 10 ** (digit - 2) - 1 if digit > 2 else n // 10 - 1

while digit_sum(front * 10 + 9) > n:
  front -= 1
start = front * 10 + 9

min_ctor = 0
for i in range(start, n):
  if digit_sum(i) == n:
    min_ctor = i
    break

print(min_ctor)

digit_sum 함수는 분해합 구하는 함수

ex. 256 (= 245 +2 + 4 + 5)

 

접근 방식

주어진 값 n이 216이라면 209, 199, 189처럼 끝이 9로 끝나는 값들의 분해합을 구해서 이 값이 216보다 처음으로 작아지는 수를 구해서 start로 두었음

189의 분해합은 207로 216보다 작음
189 이전의 숫자들의 분해합은 무조건 207보다 작고, 절대 생성자가 될 수 없음
그래서 189 이후의 숫자들부터 시작해서 분해합을 구해보는 것

그리고 start부터 시작해서 n까지의 분해합을 구하면서 분해합이 n과 처음으로 같아지는 수를 min_ctor에 대입하고 출력하는 식으로 풀이

 

front 변수는 주어진 수(n)의 앞 두자리를 구하고 그 값에서 1을 뺀 값을 대입

ex. 216이라면 20을 구하기 위함

front에서 1을 빼서 시작하는 이유는 n의 끝자리를 9로 바꿔서 분해합을 구하면 무조건 n보다 커지기 때문
만일 n이 219인 경우에도 분해합은 219 + 2 + 1 + 9로 n을 넘기 때문에 생성자가 될 수 없음

그래서 while문에서 front * 10 + 9 식을 통해 209의 분해합을 구하고 그 값이 n보다 크면 front에서 1을 빼서 다음 199의 분해합을 구하는 식으로 반복

 

n이 216인 경우 189의 분해합 207이 처음으로 216보다 작기 때문에 189가 start가 됨

189부터 시작해서 216까지 반복문을 돌면서 최초 생성자 값을 찾음

여기서는 198의 분해합이 처음으로 216과 같기 때문에 최초이자 최소 생성자가 됨

 

생성자가 없는 경우에는 0을 출력 해야하므로 min_ctor의 초기값을 0으로 두었음

 

---

같은 논리인데 조금 더 간결하게 코드를 짜는 법

 

1. 분해합이 처음으로 n보다 작아지는 xx9값 구하기

start = max(0, n - len(str(n)) * 9)

2. 분해합 구하기

# 방법 1
sum([int(k) for k in list(str(i))]) + i
# 방법 2
sum((map(int, str(i)))) + i

 

---

효율을 추구해서 start값을 구했는데 브루트 포스는 모든 경우의 수를 고려해야하는 알고리즘이니 1부터 구하는 게 맞았을지도?