문제

양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.

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

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

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

답변

from itertools import permutations
def min_path_sum(grid):
  a = 'x'*(len(grid[0])-1) + 'y'*(len(grid)-1)
  b = set(permutations(a))
  ans = []
  for i in b:
    graph_x = 0
    graph_y = 0
    root = grid[0][0]
    for j in i:
      if j == 'x':
        graph_x += 1
        root += grid[graph_y][graph_x]
      elif j == 'y':
        graph_y += 1
        root += grid[graph_y][graph_x]
    ans.append(root)
  return min(ans)

풀이에 앞서 permutations에 대해 알아보자.

permutations & combination

permutations

from itertools import permutations
a = [1,2,3]
permute = permutations(a,2)
print(list(permute))
-> [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

permutations은 순열을 의미한다. 각 요소를 중복을 허용하지 않으며 순서를 가지는 배열을 만들어 리스트로 출력한다.

combinations

from itertools import combinations
a = [1,2,3]
combi = combinations(a,2)
print(list(combi))
->[(1,2),(1,3),(2,3)]

combinations는 조합을 의미한다. 각 요소를 중복을 허용하지 않으며 순서를 가지지 않는 배열을 만들어 출력한다.

풀이

이 문제에서는 순열을 사용하였다. 인덱스가 하나씩 이동하는것을 모든 경우의 수로 만들어 이동하며 각 인덱스의 값을 더한뒤 리스트로 만들어 가장 작은 값을 출력하였다.