[Python] 백준 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을 출력한다.

 

 

코드

n = input()

min_m = int(n)-len(n)*9
check = 0
if min_m <= 0:
  min_m = 0
for i in range(min_m, int(n)):
  s_i = str(i)
  data = []
  for j in s_i:
    data.append(int(j))
  data.append(i)
  if sum(data) == int(n):
    check = 1
    break;
if check == 1:
  print(data[len(data)-1])
else:
  print(0)

 

처음엔 문제를 보고 아니 이걸 어떻게 알아? 했지만 이내 방법을 찾았다.

 

주어진 숫자의 각 자릿수는 0~9를 넘을 수 없고 

 

각 자릿수 * 9를 하면 구해야 할 생성자의 최소 범위를 알 수 있다.

 

이후 하나하나 더하면서 값을 비교하는 방법밖에 없다고 생각했다.

 

n = input()

min_m = int(n)-len(n)*9 #구해야할 값 범위의 최소값을 찾아준다.
check = 0
if min_m <= 0:
  min_m = 0 #만약 범위가 0 이하면 최소값은 0부터

우선 구해야 할 값의 최소 범위를 지정해준다.

 

for i in range(min_m, int(n)): #최소값~주어진값
  s_i = str(i) #확인해야할 값을 str으로 바꿔준다.
  data = []
  for j in s_i:
    data.append(int(j)) #각 자리수만큼 list에 넣어준다.
  data.append(i) #다 넣은 후 마지막에 현재 값을 넣어준다.
  if sum(data) == int(n): #만약 자리수 + 현재값 == 주어진 값 이면 종료
    check = 1
    break;

예제에서의 문제를 예로 들면

 

주어진 n = 256

min_m = 256 - 3*9  -> 229로 229~256 안에 구해야 할 값이 있을 수도 있고, 없을 수도 있다.

 

229부터 예를 들면

 

s_i = 229를 str 형으로 저장하고

 

data = [2, 2, 9, 229]

이렇게 4개의 값이 들어간다.

 

이후 sum(data)와 주어진 n 값을 비교한다.

 

sum(data) = 242로 주어진 n 256과 다르니 패스

 

그다음 230..231...232... 로 계속 반복한다.

 

정답의 예시인 i = 245 일 때

 

data = [2, 4, 5, 245]

sum(data) = 256으로 일치하므로 check = 1로 바꾸어주고 반복문 탈출

 

이후 가장 마지막 data값을 출력해준다.

 

만약 저기서 속도를 더 빠르게 한다면

 

for i in range(int(n), min_m, i--)

역순으로 정답을 찾거나

 

값이 없는 경우를 위해

 

if sum(data) > int(n):
	break

등을 넣어서 속도를 조금 더 높이는 방법도 있다.