[백준 2231] 분해합 - python (solved.ac - 브론즈 2)

 

백준 2231 분해합 문제

풀이

문제를 보았을때 알수있는 힌트

문제를 보면 단순하게 생각하여 10 인경우 10+각자리수(1+0)= 11 가 되는 것을 알 수 있다.

주의 할 점으로는

1. 어떤 자연수의 경우에는 생성자가 없을 수도 있다.
2. 생성자가 여러 개인 자연수가 있을 수 있다.
3. 가장 작은 생성자를 구해야 한다.

이렇게 3가지를 조심하면서 문제를 풀어야할듯하다

 

입력을 보았을때 알수있는 힌트

입력을 보았을떄 N의 최대가 100만까지 입력이 될 수 있다고 한다.

일반적으로 100만번 정도는 브루트포스 알고리즘으로 해결하는 문제일 가능성이 높다.

 

출력을 보았을때 알수있는 힌트

생성자가 없는 경우에는 0으로 출력해야 한다.

 

문제를 풀기 위한 조건 정의

이러한 힌트를 통해 나름의 조건을 세운다.

1. 생성자가 없는 경우인 0으로 결과를 초기화 해놓는다.
2. 가장 작은 생성자가 될 수 있게 작은 수(1)부터 확인하며 최대 100만까지 올라가게 한다.
3. 생성자로 분해합을 만들고 입력한 값과 비교한다.
4. 생성자의 분해합이 나온 경우 반복을 그만 하고 결과를 출력한다.

 

• 생성자가 없는 경우인 0으로 결과를 초기화

result=0

 

• 가장 작은 생성자가 될 수 있게 작은 수(1)부터 확인하며 최대 100만까지 올라가기
  • 시간 타임을 확인하기 위해서 time도 사용함

import time

start=time.time()
for i in range(1,1000000):
    temp=i
    for j in str(i):
        temp+=int(j)

print(time.time()-start)

i 는 생성자 이며 temp가 분해합이 된다.

time 결과로는 1.631711721420288 초가 나온다.

최악의 경우 100만번 돌리는데 2초 이내로 끝이 나기 때문에 시간초과 문제가 생기지 않는다. -> 브루트포스로 풀어도 되는 문제이다.

 

• 생성자로 분해합을 만들고 입력한 값과 비교하며 입력값과 같은 경우 멈춤

n= int(input())

result=0

for i in range(1,1000000):
    temp=i
    for j in str(i):
        temp+=int(j)
    if n==temp:
        result=i
        break
        
print(result)

n의 입력값을 받고 i의 생성자를 통해 temp의 분해합을 만들어서 n과 temp 값을 비교한다.

비교하며 같은 경우에 result를 생성자인 i로 변경하고 break한다.

이때, break를 하지 않으면 조건2번인 가장 작은 생성자가 아닌 다른 값이 나올수있기에 break를 통해 반복을 멈춘다.

이후 result값을 출력한다.

 

결과

 

전체 코드 공유

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2231.py