μμλ‘ μ΄λ£¨μ΄μ§ m x n
그리λκ° μΈμλ‘ λ€μ΄ μ¨λ€.
μλ¨ μΌμͺ½μμ μμνμ¬,
νλ¨ μ€λ₯Έμͺ½κΉμ§ κ°λ κΈΈμ μμλ₯Ό λ€ λνμ λ,
κ°μ₯ μμ ν©μ μ°Ύμμ return
νλΌ.
ν μ§μ μμ μ°μΈ‘μ΄λ μλλ‘λ§ μ΄λν μ μλ€.
Input: [ [1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
1β3β1β1β1 μΌλ‘ μμμ ν©μ΄ κ°μ₯ μμ
(0, 0)
μμ (1, 1)
μΌλ‘ κ°λ μ΅μ κ²½λ‘λ
(0, 1)
λ°©ν₯κ³Ό (1, 0)
λ°©ν₯ μ€
μμ μͺ½μ νν΄ λνλ κ²½μ° μ΄λ€.
(0, 1)
μμ (1, 2)
λ‘ κ°λ μ΅μ κ²½λ‘λ (0, 2)
μ (1, 1)
μ κ±°μ³ μ€λ κ²½μ° μ€ μ΅μ κ²½λ‘λ₯Ό ννλ κ²½μ°μ΄λ€.
λ§μ°¬κ°μ§λ‘
(1, 0)
μμ (2, 1)
λ‘ κ°λ μ΅μ κ²½λ‘λ (1, 1)
μ (2, 0)
μ κ±°μ³ μ€λ κ²½μ° μ€ μ΅μ κ²½λ‘λ₯Ό ννλ κ²½μ°μ΄λ€.
κ³μν΄μ
(1, 1)
μμ (3, 2)
λ‘ κ°λ μ΅μ κ²½λ‘λ (2, 1)
μ (1,2)
λ₯Ό κ±°μ³ μ€λ κ²½μ° μ€ μ΅μ κ²½λ‘λ₯Ό ννλ κ²½μ°μ΄λ€.
μ΄λ° λ°©μμΌλ‘ (0, 0)
μμ (x, y)
κΉμ§μ μ΅μ κ²½λ‘λ₯Ό λμ ν΄ λνλ©΄ μ΅μ κ²½λ‘λ₯Ό ꡬν μ μλ€.
def min_path_sum(grid):
#step1
first_columns = [element[0] for element in grid]
#step2
def sum_path(x, y):
if x == 0 and y == 0:
return grid[x][y]
elif x == 0 and y > 0:
return sum(grid[x][:y+1])
elif x > 0 and y == 0:
return sum(first_columns[:x+1])
return min(sum_path(x-1, y), sum_path(x, y-1)) + grid[x][y]
#step3
return sum_path(len(grid)-1, len(grid[0])-1)
첫λ²μ§Έ μ΄μ λμ ν΄μ λνκΈ° μμνκ² νκΈ° μν΄μ,
grid
λ₯Ό 첫 μ΄μ μμλ€μ λ΄μ 리μ€νΈλ₯Ό first_columns
μ λ΄λλ€.
μ΅μκ°μ ꡬνλ ν¨μ sum_path
λ₯Ό μ μΈ νλ€.
sum_path
ν¨μλ μ€μ²© 리μ€νΈμμ
λ΄λΆ 리μ€νΈμ ν μμμ μΈλ±μ€λ₯Ό x
,
μΈλΆ 리μ€νΈμ μΈλ±μ€λ₯Ό y
λ‘ νμ¬
(0,0)
μμ (x,y)
λ‘ μ¬ λ κΉμ§μ
μ΅μ κ²½λ‘λ₯Ό μ¬κ·μ μΈ λ°©λ²μΌλ‘ ꡬνλ μ¬κ· ν¨μλ€.
μΈλΆ ν¨μμμ sum_path(x, y)
λ₯Ό νΈμΆνκ³ λ°ν νλ€.
import time
start = time.time()
def min_path_sum(grid):
#step1
result = [[0] * len(grid[0]) for i in range(len(grid))]
first_columns = [grid[i][0] for i in range(len(grid))]
#step2
for i in range(len(result[0])):
result[0][i] = sum(grid[0][:i+1])
for i in range(len(first_columns)):
result[i][0] = sum(first_columns[:i+1])
#step3
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
result[i][j] = min(result[i-1][j], result[i][j-1]) + grid[i][j]
print(result)
print(grid)
return result[len(grid) - 1][len(grid[0])-1]
print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
print(min_path_sum([[1, 4, 5, 2], [3, 1, 2, 3]]))
end = time.time()
print(f"{end - start:.5f} sec")
κ²½λ‘μ μ΅μκ°μ λ΄μ 리μ€νΈ result
μ
grid
μ 첫 μ΄μ μμνκ² λνκΈ° μν΄,
first_columns
μ grid
μ 첫μ΄μ
μμλ§ μμλ‘ λ΄λλ€.
κ°μ₯ λ°κΉ₯ μͺ½μΌλ‘ μ΄λνλ κ²½μ°λ₯Ό κ³ λ €νκΈ° μν΄
κ°μ₯ λ°κΉ₯ μͺ½ ν, μ΄ λ°©ν₯λ§μΌλ‘ μ΄λνλ©° λμ νμ¬ result
μ λ΄λλ€.
result
μ (1,1), (1,2) ... (2,0),(2,1), ... (x, y-1), (x-1, y)
κΉμ§μ μ΅μκ°λ€μ λ΄μΌλ©°, μ΅μ’
μ μΌλ‘ (x, y)
μ κ°μ ꡬνκ³ , λ°ννλ€.