[프로그래머스 | DP] 등굣길 - Python

def solution(m, n, puddles):
    answer = 0
    
    road = [[1] * m for _ in range(n)]
    
    # Assign 0 to puddles 
    for x, y in puddles:
        # 주의 ! 문제에서 좌표는 공간좌표... 
        road[y-1][x-1] = 0
    
    # Assign 0 to unavailable road
    
    # Case 1 - puddle on first row
    for i in range(m):
        if road[0][i] == 0:
            for j in range(i+1, m):
                road[0][j] = 0
                break
    # Case 2 - puddle on first column
    for i in range(n):
        if road[i][0] == 0:
            for j in range(i+1, n):
                road[j][0] = 0
                break
    
    # DP - Find number of routes
    for i in range(1, n):
        for j in range(1, m):
            if road[i][j] != 0:
                left = road[i][j-1]
                up = road[i-1][j]
                road[i][j] = left + up
            
    answer = road[n-1][m-1] % 1000000007
    
    return answer

역대급 머리아팠던,,,,ㅜㅜ
학교다닐 때 배웠던 최단거리 찾기와 비슷하다... 고 생각하고 단순 덧셈으로 풀었는데

첫 행이나 열에 puddle이 있으면 절대로 목적지로 갈 수 없음을 간과했음

DP 자체는 까다롭지 않았으나,

• 반례 찾기
• 문제상에서의 좌표는 row/column 개념이 아니라는 것

때문에 좀 시간이 걸렸다 ㅠㅠ

문제 꼼꼼히 읽자

참고
반례 추천
TC 1, 9, 10 넘어서기