[9일차][DP] 최소합 구하기

- 문제 설명

5	2	8	8	8
4	4	8	5	8
10	9	6	3	5

위 번호판에서 오른쪽이나 아래로만 갈 수 있고 가면서 큰 수를 더했을때 최대값을 구하시오

- 입력

1 // 테스트 케이스

3 5 // 행, 렬

5 2 8 8 8 // 숫자 판

4 4 8 5 8

10 9 6 3 5

- 출력

#1 44 // 테스트 케이스, 최대합

- 입력 예시

3
3 5
5 2 8 8 8 
4 4 8 5 8 
10 9 6 3 5 
4 5
10 3 3 2 2 
9 9 10 10 2 
8 8 4 1 1 
1 4 5 6 3
20 20
11 18 3 11 19 1 8 8 19 17 4 3 18 9 9 14 14 9 17 3 
11 6 8 10 17 10 10 5 11 18 15 8 15 4 9 1 12 18 15 5 
5 14 4 16 16 11 13 18 12 16 6 15 10 20 18 12 10 13 10 9 
20 1 4 9 5 14 8 1 4 13 11 9 12 18 2 1 20 13 9 19 
16 8 9 12 1 19 6 8 16 20 1 5 15 5 17 19 5 2 20 14 
16 3 1 16 15 5 8 2 16 20 5 8 6 1 8 3 8 13 12 18 
15 14 15 9 4 12 18 10 20 6 17 12 3 14 17 17 15 19 16 2 
19 14 5 6 3 15 16 19 1 16 12 16 1 2 11 3 2 11 6 9 
9 4 10 20 5 12 10 16 3 4 15 18 2 20 20 20 2 10 9 5 
14 2 5 16 16 18 11 2 9 11 2 17 8 11 5 6 11 16 18 7 
3 8 20 13 19 7 15 3 20 19 15 12 11 14 1 14 11 13 1 16 
5 10 19 1 18 15 20 9 8 17 19 19 15 12 13 16 13 9 18 19 
15 12 13 5 18 4 6 19 19 15 6 10 3 2 18 10 6 3 20 6 
20 17 2 6 8 14 16 6 4 12 13 15 1 14 12 20 9 15 9 15 
19 16 1 11 10 17 10 7 20 17 8 8 19 19 7 16 17 8 6 20 
12 11 15 20 2 14 1 20 15 9 14 17 7 7 12 20 14 13 18 1 
4 8 10 20 14 19 2 9 6 8 11 14 10 13 10 13 8 10 2 1 
5 1 4 5 19 19 9 4 19 5 9 4 19 12 16 9 16 13 10 20 
16 8 11 3 2 20 4 3 9 8 11 5 6 11 5 17 8 1 14 12 
10 20 8 19 16 14 3 8 18 9 17 9 18 6 6 11 10 3 14 9

- 출력 예시

#1 32
#2 26
#3 283

- 코드

#include "stdio.h"

int N,M;

int numberPad[101][101];

int minSum[101][101];

#define INF 0x7fffffff

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        scanf("%d %d",&N,&M); // 행, 렬 입력 받음

        

        for(int i=0;i<=M;i++) // 첫번째 행 초기화

        {

            numberPad[0][i] = INF;

            minSum[0][i] = INF;

        }

        for(int i=0;i<=N;i++) // 첫번째 열 초기화

        {

            numberPad[i][0] = INF;

            minSum[i][0] = INF;

        }

        for(int i=1;i<=N;i++)

        {

            for(int j=1;j<=M;j++)

            {

                scanf("%d",&numberPad[i][j]); // 숫자판 채움

                minSum[i][j] = INF; // 최소합 배열 채움

            }

        }

        for (int i = 1; i<=N; i++)

        {

            for (int j=1; j<=M; j++)

            {

                int minValue = (minSum[i-1][j] < minSum[i][j-1]) ? minSum[i-1][j] : minSum[i][j-1]; // 둘중 작은 값을 찾기

                minValue = (minValue == INF) ? 0 : minValue; // 맨위와 맨 왼쪽을 INF로 채웠으므로 만약 INF라면 0으로 바꿔줌

                minSum[i][j] = minValue+numberPad[i][j]; // 최소값에서 현재값을 더함

            }

        }

        printf("#%d %d\n", tc,minSum[N][M]); // 최소합 출력

    }

    return 0;

}