백준 2231번: 분해합

✔ 풀이를 위한 아이디어

• 각 자리수의 합이 최대 얼마나 될 수 있는지 계산해서 탐색의 범위 좁히기
  
  

✔ 코드

import sys

N = int(sys.stdin.readline())

#자릿수에 따라 범위를 달리 하는 방법?
#한자리수는 9, 두자리수는 18 이런식으로 할 수 있지만 그럼 또 18 이하에서 나눠야함
rng = 54
if N < 54:
    rng = N

for i in range(rng, 0, -1):
    M = N - i
    sum = 0
    for n in str(M): #각 자리수 합을 구할 때는 이렇게 처리하면 된다
        sum += int(n)
    if sum == i:
        print(M)
        break
    elif i <= 1:
        print('0')
        break

• 사실 내가 설정한 탐색의 범위가 가장 효율적이라고 할 수는 없다. 최대의 효율로 탐색하려면 자릿수에 따라 범위를 나누되, 18 이하의 수들에 한에서 또 다른 범위를 설정해주면 된다.
• 각 자리수 합을 구할 때 저렇게 하는 것이 효율적이라는 것을 배웠다.
• 처음 시도했을 때는 54 미만의 수들을 고려하지 않아서 런타임 에러가 발생했다.

✔ 관련 개념

• 브루트 포스 알고리즘: https://hcr3066.tistory.com/26