완전탐색하는 brute force 문제이다.
먼저 1부터 N까지 모두 고려하는 방법이있다. 내가 처음으로 제출한 답이기도 하다.
예를들어 256의 생성자를 찾기위해 1부터 순차적으로 탐색해 생성자가 나오면 종료한다.
import sys
N = int(input())
def Constructor(M):
result = M
devide = list(str(M))
for i in devide:
result += int(i)
return result
if N < 10 :
print(0)
else:
num = 10
while M <= N :
if N == Constructor(M) :
print(M)
sys.exit()
M+=1
print(0)
위 코드를 답으로 제출해도 정답으로 인정되지만 아무것도 고려하지 않아 시간의 효율이 떨어진다.
두번 째 방법은 탐색의 범위를 줄여주는 방법이다.
세자리 수가 있을 때, 분해합은 생성자 + 세자릿 수 이다. (256 = 245 + 2 + 4 + 5)
각 자릿수들은 0~9 사이의 숫자이다. 즉, 자릿수의 최대값은 9
그러므로 생성자를 제외한 각 자릿수의 최대합은 9 x 3 = 27 이다.
즉, 256의 생성자가 생길 수 있는 범위를 256-27 로 줄일 수 있다. 천재들,,
import sys
N = input()
def Constructor(M):
result = M
for i in list(str(M)):
result += int(i)
return result
M = int(N)
for i in list(str(N)):
M -= 9
if M < 0:
print(0)
else:
while M <= int(N) :
if int(N) == Constructor(M):
print(M)
sys.exit()
M+=1
print(0)
두 코드를 비교했을 때 시간차이는... :)
'Algorithm > Solution' 카테고리의 다른 글
[Python] 백준 2089 (0) | 2021.03.04 |
---|---|
[Python] 백준 1442 (0) | 2021.02.25 |
[Python] 백준 6549 (0) | 2021.02.20 |
[Python] 백준 2606 (0) | 2020.09.01 |
[Python] 백준 1260 (0) | 2020.08.27 |
[Python] 백준 2231 (0) | 2020.05.03 |