프로젝트 오일러 051
일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수
지금까지 풀이한 문제들 중에서는 가장 높은 난이도의 문제입니다. 문제에서 직접적으로 드러내는 제약조건이 적어 보이기 때문에 생각을 좀 해봐야 하는 문제입니다.
제약조건
가장 중요한 힌트는 빈 칸을 숫자로 채워나가는 동안 소수가 8개 만들어져야 한다는 점입니다. 빈칸을 ’#‘으로 표현했을 때, “1#3”을 보겠습니다. 103, 113, 123, 133, 143, 153, 163, 173, 183, 193 중에서 3개는 필연적으로 자리수의 합이 3의 배수이므로, 8개의 소수를 만들지 못합니다. 자리수의 합이 3의 배수가 되지 않게 하기 위해서는 1)빈 칸의 개수는 3의 배수여야 하며 2) 고정된 수의 합은 3의 배수가 아니어야 합니다. 이렇게하면 빈 칸에 들어오는 수에 상관없이 전체 숫자의 합은 3의 배수가 아니게 됩니다.
이 조건을 포함하여 다른 몇 가지 조건을 나열해보겠습니다.
- 1의 자리에는 빈 칸이 올 수 없으며, 1, 3, 7, 9 중 하나의 숫자가 와야 합니다.
- 0이 채워져야 하므로, 첫번째 숫자 위치에도 빈칸은 올 수 없습니다.
- 빈 칸의 개수는 3의 배수입니다.
- 빈 칸이 아닌 곳의 고정된 숫자의 합은 3의 배수가 될 수 없습니다.
이러한 조건을 만족하는 가장 작은 소수를 구하라고 했기 때문에, 5자리에서 7자리 사이에 답이 있을 거라고 추측할 수 있습니다. 답이 5자리 소수라면 빈 칸의 개수는 3개일 것입니다. 답이 7자리 소수라면 빈 칸의 개수는 3개 혹은 6개가 될 수도 있습니다. 그러나 3개만 빈 칸인 경우는 6개가 빈칸인 경우보다 훨씬 소수가 많이 나올 확률이 크므로 빈 칸의 수는 3으로 고정하겠습니다.
운이 나쁘다면 이 범위 내에서 답을 찾지 못할 수 있겠지만, 일단 시도해보고 범위는 변경하면 됩니다.
템플릿 만들기
편의상 5자리 수에서 2개의 고정된 숫자가 있다고 합시다. 원소 5개인 집합에서 만들 수 있는 순열의 수는 5!=120개나 됩니다만 실제로 빈 칸끼리는 순서가 상관없기 때문에 20개의 순열을 만들 수 있습니다. 물론 이 중에서 첫번째 자리와 끝자리에 대한 제약을 적용하면 실제로 시험해봐야하는 템플릿의 경우의 수를 더 많이 줄일 수 있습니다.
중복된 원소를 포함하는 순열의 수는 쉽게 계산할 수 있지만, 그 순열을 생성하는 것은 직접 구현해야 합니다. 우리는 앞선 문제에서 순열 생성기를 직접 구현하였는데, 그 아이디어를 사용하면 조합, 중복조합, 중복순열, 중복을 포함하는 원소에 대한 순열을 모두 구현할 수 있습니다.
특히 파이썬 3.8이상에서는 사전과 사전으로부터 파생된 여러 집합들이 키가 추가된 순서를 유지하기에 더욱 간단하게 구현할 수 있습니다.
순열을 생성하는 코드에서는 이미 사용한 원소를 빼고 나머지 원소로 만들 수 있는 순열을 뒤에 붙인다는 개념을 사용했습니다. 여기서는 중복된 원소끼리의 순열을 배제해야 하므로, 원소와 그 개수의 순서쌍을 이용합니다. collections.Counter를 사용하면 이를 좀 더 수월하게 구현할 수 있습니다.
그리고 이 문제의 목적에 맞게, 0이나 빈 칸으로 시작하거나, 끝자리에 올 수 없는 문자가 있는 경우를 제외하고 생성하도록 구현합니다.
def generate_template(ns: list[int], blanks: int = 3):
"""
중복된 요소를 포함하는 리스트의 순열
ns: 빈 칸이 아닌 자리의 숫자들
blanks: 빈 칸의 개수
"""
# 빈 칸이 아닌 숫자들의 합은 3의 배수가 되면 안됩니다.
if sum(ns) % 3 == 0:
return
def helper(
acc: list[str], remains: dict[str, int], k: int
) -> Generator[str, None, None]:
if k == 0:
# 첫자리, 끝자리에 올 수 없는 경우 제외
if acc[0] != "0" and acc[0] != "*" and acc[-1] in "1379":
yield "".join(acc)
return
for key, v in remains.items():
if v == 0:
continue
yield from helper([*acc, key], {**remains, key: v - 1}, k - 1)
# 주어진 숫자와 필요한 만큼의 공백(*)으로 리스트를 만들고, 중복된 원소에 대한 순열 생성
xs = list(map(str, ns)) + ["*"] * blanks
counter = Counter(xs)
yield from helper([], counter, len(xs))이 제너레이터로 생성한 각 템플릿에 대해 9개의 숫자를 생성하는 제너레이터는 다음과 같이 구현합니다.
def produce(template: str) -> Generator[int, None, None]:
"""주어진 템플릿에서 공백을 0~9로 치환한 정수 집합"""
for i in range(10):
yield int(template.replace('*', str(i)))중복 조합
템플릿을 생성하기 위한 고정 숫자들을 생성하는 작업도 필요합니다. 그런데, 23###으로부터 생성할 수 있는 템플릿과 32###으로부터 생성할 수 있는 템플릿은 결국 같습니다. 따라서 불필요한 반복을 줄이기 위해서는 0~9 숫자로부터 지정된 개수만큼의 중복조합을 생성해야 합니다.
중복조합 생성기는 순열 생성기와 거의 같습니다. 앞서 사용한 원소는 재사용하지 않지만, 막 선택한 원소는 다음 레벨에서도 사용할 수 있도록 해주면 됩니다.
def combinations_with_duplication[T](xs: list[T], k=0) -> Generator[list[T], None, None]:
"""중복을 허용하는 조합 생성기"""
def helper(head: list[T], tail: list[T], k: int):
if k == 0:
yield head
return
for i, x in enumerate(tail):
yield from helper([*head, x], tail[i:], k - 1)
yield from helper([], xs, k if k > 0 else len(xs))최종 풀이
이제 문제 풀이에 필요한 모든 요소는 준비가 되었습니다. 고정 숫자는 2자리부터 7자리까지 범위로하고 빈 칸의 수는 3으로 잡고 탐색을 시작합니다. 미리 결론을 이야기하자면 이 범위에서 답을 찾을 수 있고, 걱정했던 것보다 우리가 작성한 코드는 상당히 효율적입니다.
def main():
for n in range(2, 8):
for xs in combinations_with_duplication(list(range(10)), n):
for ts in generate_template(xs, 3):
ps = [p for p in produce(ts) if isprime(p)]
if len(ps) == 8:
print(ps[0])
return