[10/19] 등굣길

레벨3 문제
DP

내 코드

def solution(m, n, puddles):
    arr = [[0] * m for _ in range(n)]
    arr[0][0] = 1
    
    # 물웅덩이 좌표 입력
    for w, h in puddles:
        arr[h-1][w-1] = -1
    
    for h in range(n):
        # 첫번째 행
        if (h == 0):
            for w in range(1, m):
                # 현재 좌표가 물웅덩이라면
                if (arr[h][w] == -1):
                    arr[h][w] = 0
                else:
                    arr[h][w] = arr[h][w-1]
            
        # 나머지 행
        else:
            for w in range(m):
                # 나머지 행의 첫번째 열
                if (w == 0):
                    if (arr[h][w] == -1):
                        arr[h][w] = 0
                    else:
                        arr[h][w] = arr[h-1][w]
                
                # 나머지 행의 나머지 열
                else:
                    # 물웅덩이라면
                    if ( arr[h][w] == -1 ):
                        arr[h][w] = 0
                    else:
                        arr[h][w] = ( arr[h-1][w] + arr[h][w-1] ) % 1000000007
    
    answer = arr[-1][-1]
    return answer

로직

• DP + 메모이제이션
• [0][0]은 1, 물웅덩이는 -1, 나머지 좌표는 0으로 지정

피드백

• 나머지 법칙? 공부(숙지) 필요