[프로그래머스-동적계획법] 등굣길_파이썬 ❌🔺

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

---

def solution(m, n, puddles):
    graph = [[0]*(m+1) for _ in range(n+1)]
    graph[1][1] = 1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [j, i] in puddles:
                graph[i][j] = 0
            else:
                graph[i][j] = graph[i-1][j] + graph[i][j-1]
    
    return graph[n][m] % 1000000007

 

• m = 4; n = 3; puddles = [[2, 2]]

0	0	0	0	0
0	집(1)	1	1	1
0	1	물(0)	1	2
0	1	1	2	학교(4)

오른쪽과 아래쪽으로만 움직일 수 있으므로, 왼쪽과 위쪽을 더한 값이 최적의 경로 합이된다.

따라서 graph[i][j] = graph[i-1][j] + graph[i][j-1] 공식이 만들어진다.

def solution(m, n, puddles):
    grid = [[0]*(m+1) for _ in range(n+1)]
    grid[1][1] = 1
    
    for i in range(n+1):
        for j in range(m+1):
            if [i, j] == [1, 1] or [j, i] in puddles:
                continue
            grid[i][j] = grid[i-1][j] + grid[i][j-1]
    
    return grid[n][m] % 1000000007