파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 32번 문제 - pandigital product

1부터 n까지 연속된 정수를 한번씩만 사용해서, n자리 수를 만들면, 그수는 pandigital 이라고 합니다. 예를 들면 15234 는 5의 pandigital 입니다.

문제는 39 x 186 = 7254 처럼 AxB=C 를 만족하면서 세수 A,B,C의 자릿수들을 모두 이으면 1부터 9의 pandigital 이 되는 C를 모두 찾아서 합을 구하는 것입니다.

 

여러가지 방법이 있겠지만, 일단 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

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기