8. Largest product in a series

1. 개요

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

2. Ver 1.0

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

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이다.