[C/C++] 프로젝트 오일러 #81 Path sum : two ways(동적 계획법)

이 문제는 난이도 10% 문제로, 그래프 이론을 이용해서 풀어도 되겠지만, 기본 자체가 동적 계획법을 이용하는 것이 더 쉽습니다.

 

path sum

시작점은 왼쪽 위의 지점이고, 오른쪽과 아래로만 이동할 수 있고, 도착점은 오른쪽 아래의 지점입니다.  다양한 경로가 나올 수 있는데, 이 때, 최대의 값을 찾는 프로그램을 작성하면 됩니다.

 

\[
\begin{pmatrix}
\color{red}{131} & 673 & 234 & 103 & 18\\
\color{red}{201}  & \color{red}{96} & \color{red}{342} & 965 & 150\\
630 & 803 & \color{red}{746} & \color{red}{422} & 111\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 &  524 &\color{red}{37} & \color{red}{331}
\end{pmatrix}
\]

 

문제로 주어진 행렬은 파일로 주어지기 때문에, 이 파일을 읽어서 수행해야 합니다.  \((r, c)\) 위치의 값을 얻기 위해서는 다음과 같은 점화식을 사용합니다.

 

\[ d_{(1, 1)} = m_{{1, 1}}, d_{(0, c)} = 0, d_{(r, c)} = 0\]

\[ d_{(r, c)} = max( d_{(r-1, c)}, d_{(r, c-1)} ) + m_{(r, c)}  \]

 

아래는 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FN   "p081_matrix.txt"
int main()
{
    int mt[80][80];

    //  read file
    {
        FILE *fi = fopen(FN, "r");
        char str[1024];
        for( int i = 0 ; i < 80 ; i++ )
        {
            fgets(str, 1024, fi);
            int c = 0;
            for( char *p = strtok(str, ", \n") ; p ; p = strtok(0, ", \n"))
                mt[i][c++] = atoi(p);
        }
        fclose(fi);
    }
    for( int i = 1 ; i < 80 ; i++ )
    {
        mt[i][0] += mt[i-1][0];
        mt[0][i] += mt[0][i-1];
    }
    for( int i = 1 ; i < 80 ; i++ )
    {
        for( int j = 1 ; j < 80 ; j++ )
        {
            mt[i][j] += (mt[i-1][j]<mt[i][j-1])?mt[i-1][j]:mt[i][j-1];
        }
    }
    printf("ans = %d\n", mt[79][79]);
}