[C/C++] 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기(동적 프로그래밍)

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

Project Euler의 18번 문제는 삼각형 숫자 배열에서 위에서 아래로 내려오는 경로 중 합이 최대가 되는 경로를 찾는 문제입니다.

문제에서 주어진 삼각형 숫자 배열에서 맨 위 숫자에서 시작하여 아래로 내려오면서 인접한 두 숫자 중 하나를 선택하여 이동합니다. 이때, 선택한 숫자들의 합이 최대가 되는 경로를 찾아 그 합을 구하는 것이 목표입니다.

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

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

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

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

[실행결과]

 

 

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

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

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

 

path sum

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

//------------------------------------------------
//    Project Euler #18 - Maximum Path Sum I
//        - by Aubrey Choi
//        - created at 2015-01-14
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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');
    }
}