[ Project Euler With Python ] 8. Largest product in a series

원문 : Largest product in a series

---

The four adjacent digits in the 1000-digit number that have the greatest product are 9 x 9 x 8 x 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

1000 자리 숫자 내에서 인접한 네 개의 숫자 중에 그것의곱이 가장 큰 것은 9 x 9 x 8 x 9 = 5832 입니다.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

1000 자리 숫자의 인접한 13 개의 숫자들 중에서 곱이 가장 큰 것을 찾으십시오. 그 곱의 값은 무엇입니까?

일단 간단하게 생각하면 그냥 루프를 돌면서 15 개씩 묶어서 곱해보는 것이 가장 단순합니다. 먼저 하나의 1000 자리 숫자를 여러 개의 1 자리 숫자로 나누는 작업이 필요하겠죠.

그런데 이 작업을 하려면 1000 자리가 들어 갈 수 있는 자료형이 필요합니다. 컴퓨터는 데이터를 이진수로 저장하기 때문에, 이를 표현하기 위해서는 얼마나 큰 비트가 필요할까요?

계산을 해 보도록 하겠습니다.

이진수로 자리수를 올리는 것은 한 비트씩 옮기는 겁니다. 아래 첨자가 2 라고 되어 있으면 이진수를 그렇지 않으면 십진수를 의미합니다.

그렇다면 십진수는 어떨까요( 아래에서 왼쪽 항을 볼 때 주의할 점은 십진수 표현이라는 것입니다. 줄을 맞추려고 앞에 0 을 넣었습니다. 아래 첨자가 없다는 점에 주의하세요 ).

그럼 10 의 멱승을 이진수로 표현해 보죠.

뭔가 규칙이 있을까요? 십진수가 1 자리 올라갈 때마다, 이진수는 3 자리나 4 자리가 올라가는 것을 알 수 있습니다. 이렇게 볼 때 십진수로 표현했을 때 1000 자리가 되려면 이진수로 고쳤을 때 최대 4000 자리( 즉 4000 비트 )가 필요함을 알 수 있습니다.

즉 1000 자리 숫자는 현재의 이진수 컴퓨팅 환경에서 표현하는 것이 불가능한 숫자입니다.

Brute-Force

그래서 이를 그냥 문자열로 표현하기로 했습니다. 그리고 계산할 때마다 형변환하는 것을 피하기 위해서 미리 형변환해서 리스트에 넣었습니다. 계산 방식 자체는 단순합니다. 그냥 처음부터 13 개씩 계산하면 됩니다.

str_num = ( "73167176531330624919225119674426574742355349194934" "96983520312774506326239578318016984801869478851843" "85861560789112949495459501737958331952853208805511" "12540698747158523863050715693290963295227443043557" "66896648950445244523161731856403098711121722383113" "62229893423380308135336276614282806444486645238749" "30358907296290491560440772390713810515859307960866" "70172427121883998797908792274921901699720888093776" "65727333001053367881220235421809751254540594752243" "52584907711670556013604839586446706324415722155397" "53697817977846174064955149290862569321978468622482" "83972241375657056057490261407972968652414535100474" "82166370484403199890008895243450658541227588666881" "16427171479924442928230863465674813919123162824586" "17866458359124566529476545682848912883142607690042" "24219022671055626321111109370544217506941658960408" "07198403850962455444362981230987879927244284909188" "84580156166097919133875499200524063689912560717606" "05886116467109405077541002256983155200055935729725" "71636269561882670428252483600823257530420752963450" ) nums = list() for c in str_num : nums.append( int( c ) ) max_product = 0 offset = 0 num_adjacency = 13 max_offset = len( nums ) - num_adjacency - 1 while( offset < max_offset ) : product = 1 for i in range( offset, offset + num_adjacency ) : product *= nums[ i ] max_product = max( max_product, product ) offset += 1 print( max_product )

답은 23514624000 입니다.

Optimization

하지만 다른 문제들처럼 뭔가 다른 빠른 방법이 있을 것이라는 강박관념이 들더군요.

MathBlog 의 [ Solution to Problem 8 of Project Euler ] 의 댓글을 보니, 마지막 곱들을 저장해 놓는 것에 대한 이야기가 있었습니다. 

그렇다면 이전의 곱셈 결과에서 이전의 시작값을 나누고 다음에 올 값을 곱한다면, 문제가 해결될 수 있겠다는 생각이 들더군요. 그런데 실제 해 보니 안 됐습니다. 중간에 0 이 있으면 모든 값이 무산된다는 것을 고려하지 않은거죠. 만약 0 인 숫자가 하나도 없다면 가능할 것 같네요.

Other's Solution

[ Project Euler 8: Find the largest product of 13 consecutive digits ] 에서는 파이썬의 언어특성을 잘 이용해서 매우 짧은 코드를 작성하고 있습니다.

#Project Euler Problem 8 from operator import mul d = map(int, ''.join(line.rstrip() for line in open('pe8.txt'))) L = 13 print 'Greatest product of', L, 'consecutive \ndigits =', print "None." if L>len(d) else \ max(reduce(mul, d[i:i+L]) for i in xrange(len(d)-L+1))

솔직히 파이썬 자료구조와 알고리즘에 대한 공부를 많이 안해서 이해하기가 힘드네요.