프로젝트 오일러 038

문제

38번 문제

어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 수

사이냅소프트

접근

어떤 자연수 N에 대해서, ×1, ×2, ×3.. 을 하면서 그 결과를 문자열로 보관하여 자릿수(글자수)의 합이 9이상이 될 때, 팬디지털인지 확인해보면 됩니다. 원래 팬디지털의 정의는 "각 진법에서 모든 숫자가 한 번 이상 사용된 숫자"이기 때문에 팬디지털의 원래 개념은 10자리 이상의 수여야 합니다.

N에 대해 문제의 조건으로 1, 2, 3, ... 의 자연수의 곱을 이어붙여 9자 이상이 될 때 팬디지털인지 검사하는 함수는 아래와 같이 작성할 수 있습니다. 조건 여부와 이 때의 결과를 같이 리턴하게 합니다.

def check(n: int) -> tuple[bool, str]:
    """
    자연수 n에 대해서
    n × 1 = a1
    n × 2 = a2
    n × 3 = a3
    ...
    를 했을 때, a1a2···ak 를 이어붙인 결과가
    1-9 팬디지털인지 확인하여,
    그 여부와 이어붙인 결과를 함께 리턴
    """
    res = []
    for j in range(1, 10):
        res.append(str(n * j))
        if sum(map(len, res)) >= 9:
            s = ''.join(res)
            return (''.join(sorted(s)) == '123456789', s)
    return (False, "")

범위

자연수 N이 5자리 수라면 1과 2를 곱한 결과는 최소 10자리가 되어 1-9가 한 번씩만 쓰인 숫자를 만들 수 없습니다. 따라서 N의 최대 범위는 4자리 숫자인 9999가 한계가 됩니다.

• [4자리수] × 1 = [4자리수]
• [4자리수] × 2 = [4~5자리수]

최대 범위가 정해졌으니, 최대값은 간단하게 구하면 됩니다.

print(max(check(n) for n in range(1, 10000)))