백준(BOJ) - 분해합(2231번) - 파이썬(python)

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력 1 

216

예제 출력 1

198

 

동적계획법(dp)을 사용하여 풀었다

 

import sys
input=sys.stdin.readline

# num의 분해합 구해서 return해주는 함수
def bun(num):
    tmp=str(num)
    sum_=0
    for x in tmp:
        sum_+=int(x)
    return num+sum_

n=int(input().rstrip())

arr=[0]*101000

for i in range(1,n+1):
    b=bun(i)
    # 최초로 생성자를 가질때(arr[b]가 0일때)가 가장 작은 생성자이다.
    if arr[b]==0:
        arr[b]=i

print(arr[n])

다른 풀이 방법 - dp를 안써도 가능. 메모리 사용량 훨씬 적다.

import sys
input=sys.stdin.readline

def bun(num):
    tmp=str(num)
    sum_=0
    for x in tmp:
        sum_+=int(x)
    return num+sum_

n=int(input().rstrip())

for i in range(1,n+1):
    b=bun(i)
    # i가 작은 수 부터 차례로 들어가므로 처음 분해합과 n이 같을 때 가장 작은 생성자를 가지고
    # 이때의 i값이 n의 생성자이다.
    if b==n:
        print(i)
        break
    # i값이 n까지 왔으면 생성자가 없다는 의미    
    if i==n:
        print(0)

 

참고 : https://velog.io/@goplanit/Algorithm-%EB%B0%B1%EC%A4%80-2231%EB%B2%88-%EB%B6%84%ED%95%B4%ED%95%A9%ED%8C%8C%EC%9D%B4%EC%8D%AC

[Algorithm] 백준 2231번 분해합(파이썬)