[Python] 백준 2231

 

 

 

 

완전탐색하는 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)

 

 

두 코드를 비교했을 때 시간차이는... :)