[Python] 백준 2231번 분해합

분해합 성공한국어

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192 MB	17950	9213	7620	50.675%

문제

어떤 자연수 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

소스코드

n = input()
num = int(n)
start = max(num - 9*len(n),0)
res = []
for i in range(start, num):
    if num == sum(map(int,str(i)))+i:
        res.append(i)
if len(res) == 0 :
    print(0)
else:
    print(min(res))

• 결과

  • 메모리 : 29284 KB
  • 시간 : 52 ms

• 문제 풀이

  • 어떤 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미합니다. 즉 245의 분해합은 245 + 2 + 4 + 5 = 256입니다. 246의 분해합은 256, 256의 생성자는 245 입니다.
  • 각 경우를 모두 확인하면 너무 오래걸리므로 각 자리값이 가장 작은 부분부터 찾습니다.
  • 각 자리의 숫자는 0~9까지 올 수 있습니다. 따라서 가장 최악의 경우를 생각해서 9 * 자릿수 만큼을 뺀 값에서 부터 분해합을 구해서 원하는 분해합값이 나오는지 확인합니다. 9*자릿수 보다 작은 경우들은 0부터 찾아야합니다.
  • 시작 부분을 찾았으면 해당 숫자에서부터 타겟 분해합까지의 숫자들의 분해합을 구합니다. 그 중에서 가장 큰 값을 출력합니다.

• 문제 출처

  • https://www.acmicpc.net/problem/2231

2231번: 분해합