[Baekjoon] 2231. 분해합

문제

https://www.acmicpc.net/problem/2231
m은 n의 생성자
m의 분해합은 n
n = 256 (245 + 2 + 4 + 5)
m = 245

🔍 1. 내 답

n = int(input())
ans = []

for m in range(n, 0, -1):
    mlist = list(map(int, str(m)))
    
    if n == m + sum(mlist):
        ans.append(m)

ans.sort()
if not ans: #리스트가 비어있는 경우
    print("0")
else:
    print(ans[0])

📌 코드 설명

m은 n의 생성자
m의 분해합은 n
n = 256 (245 + 2 + 4 + 5)
m = 245

n = m + (m의각자릿수합)
m의 값은 무조건 n이하가 된다.
1~n까지 for문을 돌려 하나씩 m인지 확인해본다.

가장 간단한 방법이지만 모든 경우에 대입해보는것이기 때문에 시간이 많이걸린다.

🔍 2. 내 답 (더 빠른)

#분해합 - 내답2 (더 빠른)

n = int(input())
ans = []

limit = n - len(str(n))*9
if limit < 0 :
    limit = 1

for m in range(limit, n):
    mlist = list(map(int, str(m)))
    
    if n == m + sum(mlist):
        ans.append(m)

if not ans: #리스트가 비어있는 경우
    print("0")
else:
    ans.sort()
    print(ans[0])

📌 코드설명

ex) n이 3자리수인 경우
n = m + (각자릿수더한값)
이때, 각 자릿수를 더한 값의 최댓값은 18 = 9+9+9
(n이 3자리수이므로 m도 최대 3자리수가 될 수있으므로)

n의 최소값은? => n - 18

수식으로 정리하면 : n의 최솟값 = n - (n의자릿수 * 9)

하지만, 이렇게할 경우 n의 최솟값이 음수가 나오는 경우가 있다.
ex) n = 13
n의 최솟값 = 13 - 2*9 = -5
따라서, 음수가 나오면 1부터 n-1까지 탐색한다.

음수가 아닐 경우 위의 최솟값계산식대로 n의최소값 ~ n-1까지 탐색한다.

🌀 list의 요소를 모두 int로 변환

#list_a = ['1', '2', '3', '4']   -> list_a = [1, 2, 3, 4] 로 바꾸고 싶을 때,
list_a = ['1', '2', '3', '4']
list_a = list(map(int, list_a))
print(list_a)

🌀 list가 비어있는지(empty) 확인하는 법

list_empty = []
if not list_empty: #list_empty가 비어있는 경우
    print("list_empty는 비어있습니다.")

🌀 list의 모든 요소를 더하기 : sum(list)

i = [1, 2, 3, 4, 5]
print(sum(i))

🌀 어떤 정수의 각 자릿수의 합 구하기

위의 개념을 모두 종합한 결과 아래와 같이 구할 수 있다.

m = 123
mlist = list(map(int, str(m)))
print(sum(mlist)) # 6 = 1+2+3