프로젝트 오일러 032

문제

32번 문제

1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

사이냅소프트

1-9 팬디지털 곱셈식

두 한 자리 수를 곱한 결과는 최대 81이므로 (9 × 9 = 81) 최대 4자리 수까지만 만들 수 있습니다. (물론 이 중에 1-4 팬디지털 곱셈식도 있습니다.) 곱셈식이 9자리가 되려면 어떤 경우들이 있을까요?

• 1자리 수 × 4자리 수 = 4자리 수
• 2자리 수 x 3자리 수 = 4자리 수

3자리 수 와 3자리 수를 곱하면 최소 5자리가 나오기 때문에 더 이상 펜디지털 곱셈식을 만들지 못합니다. 그리고 2자리 수와 3자리 수를 곱했을 때에도 5자리 수가 나올 수 있으므로 이런 상황이 있으면 루프를 조금 더 빨리 탈출시키는 방법 등으로 반복 횟수를 최대한 줄이면 됩니다.

하나의 수가 두 가지 이상의 조합의 곱으로 표현되는 것은 1개로 본다고 했으므로, 곱셈식의 결과만 중복 없이 모아주면 됩니다. set을 이용하는 것이 현명하겠죠.

def main():
    res = set()
    for x in range(1, 10):
        for y in range(1000, 10000):
            z = x * y
            if x * y > 9999:
                break
            if ''.join(sorted(f'{x}{y}{z}')) == '123456789':
                res.add(z)
    for x in range(10, 100):
        for y in range(100, 1000):
            z = x * y
            if z > 9999:
                break
            if ''.join(sorted(f'{x}{y}{z}')) == '123456789':
                res.add(z)
    return sum(res)


print(main())

이 앞 문제(영국 동전)가 제법 난이도가 있었기 때문에, 잠깐 쉬어가는 느낌인 것 같습니다.