8. Largest product in a series

1. 개요

문제는 이곳에서 확인할 수 있다.
어떤 숫자 더미에서 인접한 13개의 숫자들의 곱의 최대값을 찾는 것이 목적이다.

2. Ver 1.0

여려운 문제는 아니었지만 생각보다 시간이 오래 걸렸다. 로직은 옳은 것 같은데 계속 답이 틀렸기 때문이다.
알고보니 인접한 숫자들을 곱할 때 그 결과를 int로 지정한 것이 잘못이었다. 그 곱이 int가 처리할 수 있는 범위를 넘어섰기 때문이다. 정수라고 하면 흔히 int로 선언하곤 했고 여기서 문제가 생긴 적이 없어서 쉽게 발견하지 못했다.
int 대신 ulong을 사용하여 문제를 해결하였다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

using System; using System.Text.RegularExpressions; using System.Linq;   class ProjectEuler {     static void Main(string[] args)     {         // 1. 1000자리 숫자를 읽는다.         string data = @"73167176531330624919225119674426574742355349194934                         96983520312774506326239578318016984801869478851843                         85861560789112949495459501737958331952853208805511                         12540698747158523863050715693290963295227443043557                         66896648950445244523161731856403098711121722383113                         62229893423380308135336276614282806444486645238749                         30358907296290491560440772390713810515859307960866                         70172427121883998797908792274921901699720888093776                         65727333001053367881220235421809751254540594752243                         52584907711670556013604839586446706324415722155397                         53697817977846174064955149290862569321978468622482                         83972241375657056057490261407972968652414535100474                         82166370484403199890008895243450658541227588666881                         16427171479924442928230863465674813919123162824586                         17866458359124566529476545682848912883142607690042                         24219022671055626321111109370544217506941658960408                         07198403850962455444362981230987879927244284909188                         84580156166097919133875499200524063689912560717606                         05886116467109405077541002256983155200055935729725                         71636269561882670428252483600823257530420752963450";         data = Regex.Replace(data,"[\n\r\t]",string.Empty);                   // 2. k개의 인접한 수를 곱해가면서 답을 찾는다.         // 단, 인접한 수에 0이 포함되어 있다면 계산하지 않는다.         int k = 13;         int i = 0;         ulong max_prod = 0;                   while(i < data.Length-k+1)         {             string temp_data = data.Substring(i,k);             int position_zero = temp_data.LastIndexOf("0");                           if(position_zero > -1)             {                 i += position_zero + 1;                 continue;             }                           // Overflow를 방지하기 위하여 int보다 큰 자료형을 사용한다.             ulong prod = temp_data.Aggregate(1UL, (n,m) => n*(ulong)Char.GetNumericValue(m));                           if(max_prod < prod)             {                 max_prod = prod;                 Console.WriteLine("Adjacent "+ Convert.ToString(k) + "-digits: " + temp_data);                 Console.WriteLine("Value: " + Convert.ToString(max_prod) + "\n");             }                           i++;         }     } }

답은 23514624000이다.