2018년 4월 21일 토요일

무게가 있는 길찾기 [C 언어]

#include 

#define M 100
#define N 100

int map[M][N];

int max(int x, int y)
{
  if (x > y)
    return x;
  return y;
}

int max_joy(int m, int n)
{
  if (m == 0 && n == 0) {
    return map[0][0];
  }
  // 맨 위인경우.
  if (m == 0) {
    return max_joy(m, n-1) + map[m][n];
  }
  // 맨 왼쪽인경우.
  if (n == 0) {
    return max_joy(m-1, n) + map[m][n];
  }
  // 위,왼 중에 max를 골라서 더함.
  return max(max_joy(m-1, n), max_joy(m, n-1)) + map[m][n];
}

int joy[M][N];
void dynamic_joy(int m, int n)
{
  int i, j;
  
  joy[0][0] = map[0][0]; // 0,0 처음세팅.
  // 맨위,맨왼 세팅
  for (i = 1; i < m; ++i) {
    joy[i][0] = joy[i-1][0] + map[i][0];
  }
  for (j = 1; j < n; ++j) {
    joy[0][j] = joy[0][j-1] + map[0][j];
  }
  
  // 그 사이들 세팅.
  for (i = 1; i < m; ++i)
    for (j = 1; j < n; ++j)
      joy[i][j] = max(joy[i-1][j], joy[i][j-1]) + map[i][j];
}

/*
5 5
1 2 2 1 5
1 4 4 3 1
2 1 1 1 2
1 3 5 1 1
1 5 1 2 2
*/
int main() {
  int m, n, i, j;
  
  scanf("%d %d", &m, &n);
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &map[i][j]);
  printf("%d\n", max_joy(m-1, n-1));
  
  dynamic_joy(m, n);
  
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++)
      printf("%d ", joy[i][j]);
    printf("\n");
  }
  return 0;
}

댓글 없음 :

댓글 쓰기