14. 프로젝트 오일러 #14 : 최대 체인을 가지는 우박수 구하기

이번 문제는 동적 프로그래밍을 이용해서 작성을 하는 것이 가장 좋을 듯 합니다.

우박수를 구하다보면, 이미 전에 계산했던 우박수 체인수가 있을 수 있습니다.  그렇게 하지 않으면, 체인수가 100여개 있는데, 1,000,000까지 구한다면, 1억번정도 평균적으로 계산해야 합니다.  동적 프로그래밍을 이용하면, 이 수를 줄일 수 있습니다.  물론 수가 1이 된다는 가정하에서 이야기지만, 현재까지 예외는 없으니까요.

사실 수학적으로 1,000,000까지 우박수가 된다는 것을 확인하면, n/2로 건너뛰기를 하기 때문에 반드시 우박수가 될 수밖에 없습니다.  순수한 수학적인 증명만으로는 할 수 없지만요.

물론, 자꾸 홀수에 걸쳐서 숫자가 비대해질 수는 있습니다만, 3n+1 은 반드시 짝수가 되기 때문에 홀수가 연달아 나올 수는 없습니다.  그래서 1,000,000까지 가면서, int32 형으로 가능할 것이라고 생각했었는데, 프로그램이 오류가 나서, 살펴보니, 음수로 바뀌었네요.  uint32로 될지는 모르겠지만, int64형으로 프로그램을 작성했습니다.

배열을 무작정 크게 할 수는 없어서, MAXDP를 설정해서, MAXDP보다 큰 수는 저장하지 않도록 했습니다.  사실 2의 배수에 대해서는 숫자를 빠르게 줄일 수 있기 때문에 홀수만 저장하는 방법도 고려했지만, 그러면 프로그램이 너무 복잡해질 듯 해서, 이쯤에서 마무리했습니다.

#include <stdio.h>
#define MAXDP   5000000

int getchains(int64_t n);

int main()
{
        int max = 1, k = 1;

        for( int i = 2 ; i < 1000000 ; i++ )
        {
                int c = getchains(i);
                if( c > max ) max = c, k = i;
        }
        printf("Ans = %d (%d)\n", k, max);
}

int getchains(int64_t n)
{
        static int chain[MAXDP];

        if( n == 1 ) return 1;
        if( n >= MAXDP )
        {
                if( n%2 ) return getchains(3*n+1)+1;
                else return getchains(n/2)+1;
        }
        if( chain[n] ) return chain[n];
        if( n%2 ) return chain[n] = getchains(3*n+1)+1;
        else return chain[n] = getchains(n/2)+1;
}