[Python] BAEKJOON 2231번 분해합

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을 출력한다.

예제 입력 1 

216

예제 출력 1 

198

 

해설

 

가장 기본적인 아이디어는 부르트포스. (brute force) 거창한 말같지만, 일일히 시도해보는 무식한 방식. 

for i in range(a,b)에서 i를 a부터 b-1까지 증가시켜 해당하는 N과 같은 i(t생성자)값을 찾는다.
try1)이 시간초과가 뜨는 이유는 range(a,b)범위가 너무 크기 때문. 

 

try1) 시간 초과 코드

N = input()
a= 10**(len(N)-1)
b = 10**(len(N))

def addsum(i):
    lst = [int(j) for j in str(i)]
    return sum(lst)
    
for i in range(a,b):
    total = i + addsum(i)
    if total == int(N):
        print(i)
        break 
    if i == b-1:
        print(0)

 

 

 

 sol1)에서 a를 int(N) - 9*len(N)으로, b를 int(N)으로 두었다. 각 자리의 숫자는 0~9이므로 최대 9다. 문제는 N이 17일 경우, a는 17-9*2 = -1 <0 이다. 음수인데, 자릿수를 더하는 과정은 def addsum()함수의 str(i)를 int(i)로 바꾸는 과정이기 때문에 마이너스(-)부호가 들어갈 수 없다. 따라서 조건문을 두어 a가 음수일 경우 a에 0을 대입한다. 

(1 ≤ N ≤ 1,000,000) 조건에 따라 N은 0일 수 없고, i의 범위 역시 int(N)까지일 필요가 없다. int(N) -1 까지면 된다.
따라서 b = int(N)라고 두어도 무방하다. 

sol1) brute force 1

N = input()
a= int(N) - 9*len(N)
b = int(N)

def addsum(i):
    lst = [int(j) for j in str(i)]
    return sum(lst)
    
if a < 0:
    a = 0 
    
for i in range(a,b):
    total = i + addsum(i)
    if total == int(N):
        print(i)
        break 
    if i == b-1:
        print(0)

 

나름 sol1)은 빠른 속도 안에 풀린다.

 

sol2) brute force 2

아래 방식은 다른 블로그를 참고해 작성한 것인데, 확실히 시간은 오래 걸릴 듯. i범위를 range(1,N+1)전부로 잡기 때문.

N = int(input())
totsum = 0
for i in range(1, N + 1):
  addsum = i + sum(map(int,str(i)))
  if addsum == N:
    totsum = i
    break
print(totsum)

sol2)의 코드길이는 146B로 sol1)보다 확실히 줄었는데 시간이 너무 오래 걸린다. 1200ms

 

sol3) 

sol1) 과 sol2)를 합쳤다. sol1)보다 속도는 더 빨라질 것. 왜냐면 def addsum(i) 함수 넣는 대신,
sol2)의 sum(map(int, str(i))) 로 대체했기 때문. i값을 str으로 바꿔 각 자리에 대응되는 숫자를 string list로 받았고, 이를 int로 전부 바꿔준 후(map 이용), 이 숫자를 전부 더했다.(sum()이용.)

N = input()
a= int(N) - 9*len(N)
b = int(N)

if a < 0:
    a = 0 

for i in range(a,b):
    total = i + sum(map(int,str(i)))
    if total == int(N):
        print(i)
        break 
    if i == b-1:
        print(0)

sol3)로 1등 찍었다. 걸린 시간은 32ms