[프로그래머스] Lv.3 등굣길 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42898
• 🔑 DP (동적 계획법)
  • n, m 보다 1크게 리스트를 만든다.
  • 1, 1 시작 위치에 1을 표시한다.
  • 시작 위치일때와 물에 잠긴 지역일때는 건너뛴다. continue
  • 그냥 길이면 좌표의 위 값 + 왼쪽 값을 현재 위치에 넣는다.
    • 위에서 오는 경우와 왼쪽에서 오는 경우의 합

 

def solution(m, n, puddles):
    
    MAP = [[0] * (m+1) for _ in range(n+1)]
    MAP[1][1] = 1
    
    for r in range(1, n+1):
        for c in range(1, m+1):
            if r + c == 2 or [c, r] in puddles:
                continue
            else:
                MAP[r][c] = (MAP[r-1][c] + MAP[r][c-1]) % 1_000_000_007
    
    return MAP[-1][-1]