[Algorithm] 3주차 4번 문제

✅ 문제

---

양수로 이루어진 m x n 그리드를 인자로 받습니다.

상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾는 프로그램을 작성해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input: [    [1,3,1],    [1,5,1],    [4,2,1] ]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작기 때문입니다.

📌풀이

---

문제를 이해해도 풀이 방법이 도저히 생각나지 않아

소스 코드를 찾아 이해한 내용을 적어보겠습니다..

그리드 내부에서 오른쪽이나 아래로 이동할 때마다 합의 최솟값을 추적해야합니다.

def answer(grid):
  	# 1
	for x in range(1,len(grid)):
    	grid[x][0] = grid[x][0] + grid[x-1][0]
 
    # 2
  	for x in range(1,len(grid[0])):
    	grid[0][x] = grid[0][x] + grid[0][x-1]
    # 3
  	for x in range(1,len(grid)):
    	for y in range(1,len(grid[0])):
      		grid[x][y] = grid[x][y] + min(grid[x-1][y], grid[x][y-1])
  
	return grid[len(grid)-1][len(grid[0])-1]

기존 그리드

[1,3,1]
[1,5,1]
[4,2,1] 

#1 가장 왼쪽 부분의 값을 누적한 값으로 바꾸어줍니다.

변경 된 그리드

[1,3,1]
[2,5,1]
[6,2,1] 

#2 가장 상단 부분의 값을 누적한 값으로 바꾸어줍니다.

변경 된 그리드

[1,4,5]
[2,5,1]
[6,2,1] 

#3 이제 변경된 그리드에서 더 작은 값과 더해줍니다.

변경 된 그리드에서 보면 다음과 같습니다.

[1,4,5]
[2,5,1]
[6,2,1]
     ↓
     7

기존 그리드와 비교했을 때 1 → 3 → 1 → 1 → 1 의 경로를 갖게 되고 이 요소들을 더한 값 7이 반환되는 것입니다.