18. 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기

이번 프로그램은 개인적으로도 재미있을 것 같았습니다.

가장 중요한 알고리즘은 바로 동적 프로그래밍(Dynamic Programming)입니다.  실제 경로 문제 중 최적값 찾기에는 동적 프로그래밍 기법을 자주 사용하게 되는데, 이 프로그램 역시 마찬가지입니다.

해당 사이트 문제에서도 그런 점을 언급하기는 했지만,

동적 프로그래밍을 사용하지 않는다면, 경로의 수가 많은 경우에는 매우 많은 연산을 하게 됩니다.  이번 문제는 경로의 수가 16,384가지가 나옵니다.  왜냐하면 각 층의 숫자마다 경로가 2가지씩 나오니까요.  총 15층이므로, 총 경로의 수는 가 됩니다.

그러나 동적 프로그래밍을 이용하면, 실제 경로의 수 계산은 총 숫자의 갯수인 120가지밖에 안 됩니다.  #67 문제에 100층짜리 문제가 나온다고 합니다.  100층의 경우에는 어마어마한 숫자가 되겠죠.  2의 99승이니, 어림잡아 계산해도 10의 30승 정도 됩니다.  그러나 동적 프로그래밍을 이용하면, 5,050 정도 계산량에 그칠겁니다.  (물론 메모리는 그만큼 더 쓰겠죠.)

[실행결과]

실행결과는 경로를 표시한 것까지 했습니다.  사실 답만 딱 내어도 되겠지만요.

답은 예의상 지웠습니다.  물론 인터넷 검색을 하면, 답까지 나와있는 곳도 있겠죠?

프로그램을 작성할 때, 비재귀적 프로그램으로 작성할 수도 있겠지만, 저는 재귀적 프로그램으로 작성해보았습니다.  #67 문제를 풀 때에는 재귀적 프로그램보다는 비재귀적 프로그램으로 짜보는 것이 좋다고 생각합니다.  (재귀적 프로그램은 상당히 비싼 방법이며, 또한 스택이 가득차는 불상사가 생길 수도 있습니다.)

아래에 소스를 첨부합니다.

void printtriangle(int h[], int n);
int getmax(int h[], int d[], int s, int c, int n);

int f[1000];

int main()
{
        char s[] = " 75 95 64 17 47 82 18 35 87 10 20 \
                04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 \
                67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 \
                70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 \
                25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 \
                68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 \
                63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 \
                98 27 23 09 70 98 73 93 38 53 60 04 23";

        int h[1000];
        int d[1000];
        int n = 0;

        memset(d, 0, sizeof(d));

        for( char *tok = strtok(s, " ") ; tok ; tok = strtok(0, " ") )
        {
                h[n++] = atoi(tok);
        }

        printf("Ans = %d\n", getmax(h, d, 0, 1, n));

        int c = 0;
        while( c < n )
        {
                h[c] = -h[c];
                c = f[c];
        }

        printtriangle(h, n);
}

int getmax(int h[], int d[], int s, int c, int n)
{
        if( s >= n ) return 0;
        if( d[s] ) return d[s];
        int a = getmax(h, d, s+c, c+1, n);
        int b = getmax(h, d, s+c+1, c+1, n);
        if( a > b ) { f[s] = s+c; return d[s] = a+h[s]; }
        f[s] = s+c+1; return d[s] = b+h[s];
}

void printtriangle(int h[], int n)
{
        int u = 40;
        for( int i = 0 ;  ; i++ )
        {
                int s = i*(i+1)/2;
                if( n < s+i+1 ) break;
                printf("%*s", u-i*2, "");
                for( int j = 0 ; j < i+1 ; j++ )
                {
                        if( h[s+j] < 0 ) printf("\033[1;34m%02d\033[0m ", -h[s+j]);
                        else printf("%02d  ", h[s+j]);
                }
                putchar('\n');
        }
}