오일러 프로젝트 43

오일러 프로젝트 43 번 문제는 0-9 팬디지털 숫자의 일부분이 특정한 규칙 (4번째 자리부터 세자리씩 끊었을 때 소수로 나눠짐)을 따른다고 할 때, 이런 규칙을 따르는 값 모두를 찾는 것이다.

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다. d1을 첫째 자리수, d2를 둘째 자리수…라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=43

접근

문제 자체는 사실 그리 어렵지 않은데, 경우에 따라서 성능이 문제가 될 수 있다. 따라서 다음과 같은 전략을 취한다.

1. 앞자리 숫자부터 결정한다. 이전에 쓰이지 않은 숫자 중에서 순회하면서 선결 조건을 확인한다. 이 선결 조건이라는 것은 4번째 숫자부터 n – 3 번째 소수로 나눠지는지를 검사하는 것이다. 조건을 만족한다면, 그 숫자를 포함시켜서 다음 숫자를 찾고 그렇지 않은 경우는 이후 과정을 생략한다.
2. 특정한 자리의 숫자까지 값이 결정된다 하더라도, 답이 하나가 아니다. 따라서 배열이나 세트를 이용해서 값을 수집한다.

결정된 값과 거기에 사용된 숫자. 그리고 지금 a 번째 숫자를 고르려고 할 때 필요한 가드. 이렇게 구성된 함수를 재귀호출하여 간단하게 풀 수 있는 문제이다. 물론 보다 무식한 방법(?)을 통해서 풀어도 된다.
참고로 여기서는 배열보다는 세트를 썼다.

let primes = [2, 3, 5, 7, 11, 13, 17] // 4번째 자리부터 소수로 나눠지는지 계산할 거다
func test(n: Int, seive: Set<Int>) -> Set<Int> {
  // 기저조건 : 채용한 숫자의 개수가 10개면 끝난다.
  guard sieve.count < 10 else { return [n] }
  var result: Set<Int> = []
  var d = sieve.count + 1 // 이번 단계에서 검사할 숫자가 몇 번째인지?
  let xs = (0...9).filter{ !sieve.contains($0) }
  for x in xs {
    // dn에 대하여 이전 3자리 숫자에 대한 검사
    if d > 3, case let y = (n % 100) * 10 + x, y % primes[d-4] != 0 {
      continue
    }
    var newSieve = sieve
    newSieve.insert(x)
    if case let temp = test(n: n * 10 + x , sieve: newSieve), !temp.isEmpty {
      result = result.union(temp)
    }
  }
  return result
}

처음에는 레벨값을 별도의 변수로 두려 했는데, 몇 번째 숫자를 체크할 것인가에 대해서 레벨값이 엄청 헷갈려서 그냥 이전까지 사용한 숫자의 개수로 이를 판별하도록 했다. 다음과 같이 코드가 정리되며 매우 빠르게 끝난다.

do {
  var s = 0
  for i in 1...9 { // 첫번째 숫자에는 0이 오지 않는다.
    if case ns = test(n: i, sieve: [i]), !ns.isEmpty {
      s += ns.reduce(0, +)
    }
  }
  print(n)
}

파이썬 풀이

재귀로 푸는 법은 Swift에서 확인했으니, 이번에는 무식하게 리스트 축약으로 푸는 법을 알아보자. 엄청 무식해보이기는하는데, 상당히 빠르게 계산된다.  (0.1초 대)

## Python 3.6
def check(a, b, c, d):
  return int(f"{a}{b}{c}") % d is 0
def solve():
  r = [(d1, d2, d3, d4, d5, d6, d7, d8, d9, 10)
        for d1 in range(1, 10)\
        for d2 in range(10) if d2 != d1\
        for d3 in range(10) if d3 not in (d1, d2)\
        for d4 in range(0, 10, 2) if d4 not in (d1, d2, d3)\
        for d5 in range(10) if d5 not in (d1, d2, d3, d4)\
                            and check(d3, d4, d5, 3)\
        for d6 in (0, 5) if d6 not in (d1, d2, d3, d4, d5)\
        for d7 in range(10) if d7 not in (d1, d2, d3, d4, d5, d6)\
                            and check(d5, d6, d7, 7)\
        for d8 in range(10) if d8 not in (d1, d2, d3, d4, d5, d6, d7)\
                            and check(d6, d7, d8, 11)\
        for d9 in range(10) if d9 not in (d1, d2, d3, d4, d5, d6, d7, d8)\
                            and check(d7, d8, d9, 13)\
        for d10 in range(10) if d10 not in (d1, d2, d3, d4, d5, d6, d7, d8, d9)\
                            and check(d8, d9, d10, 17)
  ]
  result = [reduce(lambda x, y: x*10+y, case) for case in r]
  print(sum(result))