1부터 n까지 연속된 정수를 한번씩만 사용해서, n자리 수를 만들면, 그수는 pandigital 이라고 합니다. 예를 들면 15234 는 5의 pandigital 입니다.
문제는 39 x 186 = 7254 처럼 AxB=C 를 만족하면서 세수 A,B,C의 자릿수들을 모두 이으면 1부터 9까지의 9자리 pandigital 이 되는 C를 모두 찾아서 합을 구하는 것입니다.
Pandigital products
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
여러가지 방법이 있겠지만, 일단 9자리 pandigital 수를 제일 작은 "123456789" 부터 시작해서, 제일 큰 "987654321" 까자 순차적으로 만들면서, 예시의 성질을 만족하는 수가 있는지를 검사하도록 하겠습니다.
먼저 pandigital 수를 만드는 함수입니다. pandigital 을 만드는 함수는 24번 문제의 순열을 만드는 함수와 동일합니다.
def get_next_permutation(string):
i=len(string)-2
while i >= 0:
if string[i] < string[i+1]:
target = sorted(string[i:])
new_num = target.pop(target.index(string[i])+1)
last_nums = ''.join(target)
return string[:i] + new_num + last_nums
i-=1
test = '123456789'
print(get_next_permutation(test))
123456798
"123456789" 숫자를 함수에 넣으면, 그다음 pandigital(또는 순열, permutation) 인 "123456798" 이 출력됩니다. 함수의 자세한 설명은 24번 문제를 참조해주세요.
그다음으로 9자리 숫자를 세부분으로 나누어서 문제에 제시된 성질(세부분의 곱셈)을 체크하는 부분입니다.
test='123456789'
for i in range(1,9):
str1=test[0:i]
for j in range(i+1,9):
str2=test[i:j]
str3=test[j:9]
print(str1,str2,str3,int(str1)*int(str2)==int(str3))
1 2 3456789 False 1 23 456789 False 1 234 56789 False 1 2345 6789 False 1 23456 789 False 1 234567 89 False 1 2345678 9 False 12 3 456789 False 12 34 56789 False 12 345 6789 False 12 3456 789 False 12 34567 89 False 12 345678 9 False 123 4 56789 False 123 45 6789 False 123 456 789 False 123 4567 89 False 123 45678 9 False 1234 5 6789 False 1234 56 789 False 1234 567 89 False 1234 5678 9 False 12345 6 789 False 12345 67 89 False 12345 678 9 False 123456 7 89 False 123456 78 9 False 1234567 8 9 False
위 계산이 하나의 pandigital에 대한 체크이고, 그다음 pandigital 수에 대해서 같은 과정을 되풀이 하면 됩니다.
성질을 만족할때(True)일때의 결과값C는 list 에 저장을 해서 마지막에 합계를 내도록 하겠습니다.
def get_next_permutation(string):
i=len(string)-2
while i >= 0:
if string[i] < string[i+1]:
target = sorted(string[i:])
new_num = target.pop(target.index(string[i])+1)
last_nums = ''.join(target)
return string[:i] + new_num + last_nums
i-=1
test = "123456789"
m=len(test)
total = []
while not test == None:
for i in range(1,m):
str1=test[0:i]
for j in range(i+1,m):
str2=test[i:j]
str3=test[j:m]
if int(str1)*int(str2)==int(str3):
print(str1,str2,str3)
total.append(int(str3))
test = get_next_permutation(test)
print(total)
12 483 5796 138 42 5796 157 28 4396 159 48 7632 1738 4 6952 18 297 5346 186 39 7254 1963 4 7852 198 27 5346 27 198 5346 28 157 4396 297 18 5346 39 186 7254 4 1738 6952 4 1963 7852 42 138 5796 48 159 7632 483 12 5796 [5796, 5796, 4396, 7632, 6952, 5346, 7254, 7852, 5346, 5346, 4396, 5346, 7254, 6952, 7852, 5796, 7632, 5796]
마지막으로 결과가 저장된 리스트에서 중복을 제외하고 합산을 하면 됩니다.
print(total) print(sum([x for i,x in enumerate(total) if total[:i].count(x)==1]))
[4396, 4396, 5346, 5346, 5346, 5346, 5796, 5796, 5796, 5796, 6952, 6952, 7254, 7254, 7632, 7632, 7852, 7852] 45228
