알고리즘 문제 11

 

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-1][j], grid[i][j-1]);
        }
    }
    return grid[grid.length-1][grid[0].length-1];
};

 

일단 가로 세로 부분은 첫번째 반복문과 두번째 반복문으로 전 index 값과 현재 index값을 더한 상태로 그리드를 바꿔놓는다

그러면 세번째 반복문에서 1,1 index부터 위 옆에 있는 값중 작은 값을 현재 값과 더해서 채워준다

이렇게 해서 마지막에서도 똑같이 위 왼쪽에 있는 값중에서 작은 값을 더해줘서 그 값을 리턴해준다.

사실 처음에는 접근방법을 아예 생각하지 못해서 풀이방법을 보고 하는데도 어려움을 겪었다. 다시 한 번 봐야 완전히 

이해될 문제이다