오일러 프로젝트 40

오일러 프로젝트 40 번 문제는 소수점 한자리부터의 숫자가 양의 정수를 차례로 붙여나간 특별한 무리수의 임의의 자리수에 관한 문제이다.

소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다. 0.123456789101112131415161718192021… 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 ( 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까?

d1 × d10 × d100 × d1,000 × d10,000 × d100,000 × d1,000,000

 

(http://euler.synap.co.kr/prob_detail.php?id=40)

접근

해당 소수의 임의의 n 자리에 대한 일반항을 세우는 것은 제법 까다로워 보인다. (어찌어찌하면 만들 수 있을 것 같기는 한데) 이런 경우에는 차라리 앞에서부터 매 자리를 만들어서 체크해나가는 것이 쉽겠다. 특히 파이썬의 제너레이터로 해당 수열 생성기를 만드는 것을 별로 어려워보이지 않는다.

  1. 1 부터 시작한다.
  2. 이 값을 문자열로 만들고 첫번째 자리부터 리턴하기 시작한다.
  3. 문자열의 마지막 글자를 리턴했다면, 1로 돌아가서 정수값을 +1 증가시킨다.

이 과정을 무한반복하는 제너레이터를 생성하고, 매 차례를 카운트하면서 1, 10, 100… 번째인 경우만 골라 담아서 곱을 구하면 된다.

제너레이터

def gen():  ## 제너레이터의 경우 몇 번째 항인지의 정보도 같이 리턴하도록 한다.
  n, step = 1, 1
  while True:
    s = str(n)
    for c in s:
      yield int(c), step
      step += 1
    n += 1

제너레이터는 생각보다 간단하다. 몇 번째 항을 얻었는지를 제너레이터 외부에서 계산하는 것은 실수의 소지가 있어서 제너레이터가 호출자에게 알려주는 편이 좀 더 편리한 디자인이라고 판단했다. 덕분의 메인 코드는 매우 간단하다.


def e40():
  g = gen()
  r = 1
  for i in range(7):
    while True:
      x, step = next(g)
      if step == 10**i :
        r *= x
        break
  print(r)
%time e40()
# Wall time: 124 ms

부록 : Swift 코드

Swift의 경우에는 이런 제너레이터를 만드는 편리한 문법이 아직까지 존재하지는 않는다. (뭐 꼭 있어야 한다는 법도 없고…) 클래스를 만들어도 되는데, 클로저를 이용해서 풀어보도록 하자. (그럼에도 불구하고 중단 위치에서 계속 이어서 수행할 수 있는 파이썬 제너레이터같은 기능이 너무 아쉽다.)

let generate: () -> (Int, Int) = {
  var n = 1
  var step = 0
  var s = String(n)
  var pos = s.startIndex
  return { () -> (Int, Int) in
    let p = Int(String(s[pos]))!
    step += 1
    pos = s.index(after:pos)
    if pos >= s.endIndex {
      n += 1
      s = String(n)
      pos = s.startIndex
    }
    return (p, step)
}()

main: do {
  var r = 1
  for i in 0..<7 {
    let l = Int(pow(10, Double(i)))
    while True {
      let (x, step) = generate()
      if step == l {
        r *= x
        break
      }
    }
  }
  print(r)
}