21.3.17

알고리즘 12일차

문제가 많이 어려움. 나중에 다시 꼭 풀이보기

• 문제 : M x N grid 주어진 이중 리스트 객체 최단 경로의 요소 합 구하기

• 풀이(리트코드 참고)

def min_path_sum(grid):
# 대전제 : 그리드 한 칸 한 칸의 값을 변경한다. 최대한 작게.
    m = len(grid)
    # 세로
    n = len(grid[0])
    # 가로
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
    # 소전제 : 가로의 값 길 구함
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    # 소전제 : 세로의 값 길 구함        
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    # 이중 for loop을 이용해서 가로, 세로 중 서로 작은 값으로 이동
    return grid[-1][-1]
    # 이동한 값의 가장 마지막 칸.

리트코드 참고 링크