[Project Euler] Problem 32

원문: Problem 32

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.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

n 자리의 수가 1부터 n까지 정확히 한번만 모든 숫자를 사용하여 만들어졌을 경우 그것을 pandigital 이라고 한다. 예를 들면, 5 자리의 수, 15234는 1부터 5까지의 pandigital 이다.

곱의 값인 7254는 특이한 숫자인데, 39 × 186 = 7254인 항등식으로, 피승수와 승수, 곱의 값이 1부터 9까지인 pandigital이다.

피승수/승수/곱의 값의 항등식이 1부터 9까지의 pandigital로 쓰여질 수 있는 모든 곱의 값의 합을 구하여라.
힌트: 몇몇 곱의 값은 한 가지 이상의 방법으로 얻어질 수 있으므로, 합계에 그것이 한 번만 포함되도록 해야한다.

수학적으로 따져보면 가능한 경우는 2자리 * 3자리 또는 1자리 * 4자리 뿐이다.
Python

def func():
    global used, Sum 

    if len(used) == 5:
        if (used[0] * 10 + used[1]) * (used[2] * 100 + used[3] * 10 + used[4]) >= 10000 \
            and used[0] * (used[1] * 1000 + used[2] * 100 + used[3] * 10 + used[4]) >= 10000:
            return

    if len(used) == 9:
        result = (used[0] * 10 + used[1]) * (used[2] * 100 + used[3] * 10 + used[4])
        if result == used[5] * 1000 + used[6] * 100 + used[7] * 10 + used[8]:
            Sum.add(result)
        result = used[0] * (used[1] * 1000 + used[2] * 100 + used[3] * 10 + used[4])
        if result == used[5] * 1000 + used[6] * 100 + used[7] * 10 + used[8]:
            Sum.add(result)
        return

    for i in range(1, 10):
        if i not in used:
            used.append(i)
            func()
            used.pop()
     

used = []
Sum = set()

func()
print(sum(Sum))

접기