최대 이익 투자 [C언어]

출처 : 문제로 풀어보는 알고리즘

#include 
/*
최대이익투자 : 문제로 풀어보는 알고리즘

4 3  투자금액, 투자 가능 기업의 수
2 3 1  기업별 1만원 투자시 이익
4 5 3  기업별 2만원
7 6 7  기업별 3만원
9 8 9  기업별 4만원

return 10 : 최대이익.
4 3
2 3 1
4 5 3
7 6 7
9 8 9
*/

#define M 100
#define N 100

int r[M][N];
int max_return[M][N];

void calculate_return(int n, int m)
{
  int i, j, k, max, t;

  // dynamic programming을 위해 미리 첫번재 기업을 세팅을 한다. (처음이니까 무조건 max)  
  for (i = 0; i <= m; i++)  {
    // 맨 윗줄.
    max_return[0][i] = r[0][i];
  }
  
  for (i = 0; i < n; i++) {
    for (j = 0; j < m+1; j++) {
      printf("%d ", r[i][j]);
    }
    printf("\n");
    
  }
  
  
  // 두번째줄부터 시작함.
  for (i = 1; i < n; i++)  // i는 기업.
    for (j = 1; j < m+1; j++) {  
    // j는 총 투자할 양 m+1인 이유는 m=0인 경우(투자안한경우)도 다뤄야 하기 때문.
    // 기업의 수(i) 투자할 양(j)를 작은 수로 시작해서 기록-> 큰 수로 간다.
      max = -1;
      for (k = 0; k <= j; k++) {  
// 이전에 투자한 회사와 액수에 대한 내용을 바탕으로 더한다.
// t = 이전 회사에 k를 투자한양과 지금 회사에 j에서 k만큼 이전회사에 투자한 양을 뺀 경우.
// 왜 계속 이전회사만하고만 비교를 하냐면 동적프로그래밍으로 계속 그 최대값이 각 배열마다 누적될 것이다. 
// 그러니 이전 내용과는 비교할 이유가 없다.
        t = max_return[i-1][k] + r[i][j - k];  // 무조건 왼쪽 + 위쪽인데.
        //printf("i=%d, j=%d, k=%d t: %d\n", i,j,k,t);
        if (t > max)
          max = t;
      }
      max_return[i][j] = max;
    }
    

}

int main(void) {
  int m, n, i, j;
  
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++)
    r[i][0] = 0;

  for (i = 1; i <= m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &r[j][i]); // 정보를 받아온다.
      
  calculate_return(n, m);
  printf("Max return: %d\n", max_return[n-1][m]);
  return 0;
}