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

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

 

path sum

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

 

$$\left(\begin{array}{ccccc}131& 673& 234& 103& 18\\ 201& 96& 342& 965& 150\\ 630& 803& 746& 422& 111\\ 537& 699& 497& 121& 956\\ 805& 732& 524& 37& 331\end{array}\right)$$

 

문제로 주어진 행렬은 파일로 주어지기 때문에, 이 파일을 읽어서 수행해야 합니다.  $(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]);
}