2231. 분해합

첫 풀이

패스이지만 만족스럽지 못하다. 아무리 브루트 포스 문제라고 해도...

216의 생성자가 두자리 수 일리가 없는데, 1부터 타겟까지 돌며 찾아 나가는게 너무 아깝다.😭😩 

뭔가 시작점을 효과적으로 설정할 수 있는 방법이 필요하다.

def f(num):
  return num + sum(map(int, list(str(num))))

N = int(input())
ans = 0
for i in range(1, N+1):
  if f(i) == N:
    ans = i
    break

print(ans)

 

최적화 풀이

각 자리수에 올 수 있는 최대 수는 9인 것을 생각해서, 타겟 숫자의 자리수*9를 계산해 시작점을 잡아줬다. 시작점을 잡아주지 않은 첫 풀이는 1440ms가 걸렸는데, 76ms로 줄였당 🥳 휴 속이 다 시원하다.

def f(num):
  return num + sum(map(int, list(str(num))))

N = int(input())
ans = 0
e = len(str(N))*9
d = N-e if N-e > 0 else 0

for i in range(d, N+1):
  if f(i) == N:
    ans = i
    break

print(ans)