[백준] 2231: 분해합 (Python)

분해합

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

2231번: 분해합

 

문제

어떤 자연수 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을 출력한다.

 

입출력 예제

입력	출력
216	198

 

풀이

1부터 n까지의 자연수에 대해 분해합이 입력된 값일 때까지 연산을 반복한다. (브루트포스)

생성자는 반드시 n보다 작거나 같으므로 n까지 연산하도록 범위를 설정했다.

각 자리의 합을 구하기 위해 각 자릿수를 정수로 형변환한 리스트를 만들어 sum 하였다.

생성자를 찾으면 출력 후 반복문을 종료하고, 반복문을 다 실행했는데도 생성자를 찾을 수 없는 경우에는 0을 출력한다.

import sys
input = sys.stdin.readline
n = int(input())
find = False
for i in range(1, n+1):
	str_i = str(i)
	temp_sum = i + sum([int(str_i[j]) for j in range(len(str_i))])
	if temp_sum == n:
		print(i)
		find = True
		break
if not find:
	print(0)

메모리: 31256 KB / 시간: 1788 ms

 

각 자릿수를 더하는 연산을 다음과 같이 map() 메소드를 이용해 처리할 수도 있다. 다음 코드는 함수형으로 작성되었다.

import sys
input = sys.stdin.readline
def getNum(n):
	num = str(n)
  ans = n
  ans += sum(map(int, num)) # sum(map(lambda x: int(x), num))
	return ans
N = int(input())
find = False
for i in range(N):
	if getNum(i) == N:
	  find = True
    print(i)
    break
if not find:
	print(0)

메모리: 31256 KB / 시간: 1084 ms

각 자릿수 숫자로 구성된 리스트를 만들어 sum하는 것보다, 문자열의 각 자릿수를 int로 형변환한 map 객체를 sum하는 것이 더 빠르게 동작했다.