8. 프로젝트 오일러 #8 : 가장 큰 곱하기 수 구하기.

이 문제는 문서에서 단어찾기에도 이용할 수 있는 문제입니다.

단어찾기의 경우에는 보통 더하기 해시를 이용하든지 하겠지만, 여기서는 곱하기이기 때문에 일단 숫자 범위가 넘어가는지 생각해보는 것도 필요합니다. 그리고 0이란 숫자가 있기 때문에 좀 골치 아픕니다.

13개의 단자리 곱셈이기 때문에 최대 숫자는 9의 13제곱인 2,541,865,828,329이 됩니다.  약 20억정도의 숫자를 표시하는 int 형으로는 오버플로우가 발생할 수 있습니다.  그래서 int64 자료형을 이용해서 프로그램을 작성해야 합니다.

4개의 숫자를 가지고 한다고 하면,

7316717653

의 숫자의 경우, 

7x3x1x6

3x1x6x7

1x6x7x1

...

과 같이 하나씩 이동하면서 4개씩 곱해주어도 됩니다.

그렇지만,

7	3	1	6
	3	1	6	7
		1	6	7	1
			6	7	1	7
				7	1	7	6

형태로 매번 3개의 곱은 늘 겹치게 됩니다.  4개의 숫자라면 곱하기를 두번 덜 하는 것이기 때문에 큰 문제가 아니라고 생각할 수 있지만, 이번 문제와 같이 13개의 숫자를 곱하는 것이라면, 12번의 곱하기를 추가로 계산해야 합니다.

그래서 제가 짠 알고리즘은

7x3x1x6

부터 시작해서

다음에는 위 수에서 곱하기에서 제거되어야 할 7을 나누고, 추가되어야 할 7을 곱하게 하였습니다.

그러나 아쉽게도 중간중간에 0이란 숫자가 있기 때문에, 0을 무시하는 대신, 0의 갯수를 항상 세도록 했습니다.  그래서 0의 갯수가 0개일 때만 최대값을 설정하도록 하였습니다.

이렇게 해서 얻어진 프로그램은 다음과 같습니다.

int main()
{
        char *s = "73167176531330624919225119674426574742355349194934"
                "96983520312774506326239578318016984801869478851843"
                "85861560789112949495459501737958331952853208805511"
                "12540698747158523863050715693290963295227443043557"
                "66896648950445244523161731856403098711121722383113"
                "62229893423380308135336276614282806444486645238749"
                "30358907296290491560440772390713810515859307960866"
                "70172427121883998797908792274921901699720888093776"
                "65727333001053367881220235421809751254540594752243"
                "52584907711670556013604839586446706324415722155397"
                "53697817977846174064955149290862569321978468622482"
                "83972241375657056057490261407972968652414535100474"
                "82166370484403199890008895243450658541227588666881"
                "16427171479924442928230863465674813919123162824586"
                "17866458359124566529476545682848912883142607690042"
                "24219022671055626321111109370544217506941658960408"
                "07198403850962455444362981230987879927244284909188"
                "84580156166097919133875499200524063689912560717606"
                "05886116467109405077541002256983155200055935729725"
                "71636269561882670428252483600823257530420752963450";
        char *h = s, *t = s;
        int64 max, c = 1, a, b, v = 0;

        for( int i = 0 ; i < 13 ; i++, t++ )
        {
                b = *t - '0';
                if( b != 0 ) c *= b;
                else v++;
        }
        if( v == 0 ) max = c;
        else max = 0;

        while( *t )
        {
                a = *h++ - '0';
                b = *t++ - '0';
                if( a != 0 ) c /= a; else v--;
                if( b != 0 ) c *= b; else v++;
                if( v == 0 && c > max ) max = c;
        }
        printf("Ans = %jd\n", max);
}

처음에 문자열로 지정을 하였는데, "1342" "2345" 와 같이 문자열을 공백문자로 나열하는 방법을 사용하였습니다.

h 포인터는 없어져야할 숫자를 가르키고 있고, t 포인터는 추가되어야 할 숫자를 가르키고 있습니다.  max는 현재 최대값, c는 현재 곱하기값, v는 0의 갯수를 저장합니다.