codecata Day3

Algorithm🤮

접근 조차못하였다. 다만 내가 문제를 조금 이상하게 생각한것같다.

문제의 의도는 N x M 의 그리드면 N번의 오른쪽이동 M번의 아래쪽이동의 최소값을 원하는것이지만

나는 어떻게 가든 최솟값이 나오게만 이동하는 것으로 이해했다.

[1,9,9,1,1,1,1]

[1,1,1,1,1,9,1]

[1,9,9,9,9,1,1]

[1,9,9,1,1,1,1]

이러한 배열은 1의 값으로만 이동하여 12의 값이 나와야한다고 생각했지만

문제에서 원하는값은 7번의 오른쪽이동 4번의 아래쪽이동으로 최솟값 18이 정답이었다.

const minPathSum = (grid) => {
  for (let i = 1; i < grid.length; i++) {
    grid[i][0] += grid[i - 1][0];
  }

  for (let i = 1; i < grid[0].length; i++) {
    grid[0][i] += grid[0][i - 1];
  }

  for (let i = 1; i < grid.length; i++) {
    for (let j = 1; j < grid[0].length; j++) {
      grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
    }
  }

  return grid[grid.length - 1][grid[0].length - 1];
};

코드해설

1번째 for문 각 인덱스의 0번째 값을 중첩하여 끝까지 계산한다.

2번째 for문 0번째인덱스 가로열의 값을 중첩하여 끝까지 계산한다.

3번째 for문 (1,2) (1,3)….(3,1) (3,2)…. (N,M)까지 해당 인덱스의 위쪽 왼쪽값중 작은값을 더하여 중첩한다.

끝~~~~