[C/C++] 프로젝트 오일러 #14 Longest Collatz Sequence(동적 프로그래밍)

1백만보다 작은 수 중에서, 다음과 같은 콜라츠 수열을 생성할 때 가장 긴 수열을 만들어내는 초기값을 찾는 문제입니다.
콜라츠 수열은 다음과 같은 규칙으로 정의됩니다:
1. 어떤 정수  n 에 대해:
•  n 이 짝수이면,  n 을 2로 나눕니다. ( n = n / 2 )
•  n 이 홀수이면,  n 에 3을 곱하고 1을 더합니다. ( n = 3n + 1 )
2. 수열은  n = 1 이 될 때 종료됩니다.

예를 들어, 초기값이 13인 경우 수열은 다음과 같이 생성됩니다:
\[ 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]
이 경우, 총 10개의 항이 있습니다.

1백만 미만의 모든 정수에 대해 가장 긴 콜라츠 수열을 만들어내는 초기값과 그 수열의 길이를 찾는 것이 목표입니다.

 

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

 

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

 

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

 

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

 

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

 

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #14 - Longest Collatz Sequence
//        - by Aubrey Choi
//        - created at 2014-12-30
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    MAXDP    5000000

int getchains(int64_t n);

int solve1()
{
    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;
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}