[프로그래머스] Lv3. 등굣길

🔗

풀이

문제분류가 DP가 아니었으면 삽질 좀 했을 것 같다. 대놓고 알려주는 문제여서 쉬웠다고 생각.

아래쪽과 오른쪽으로만 이동한다는 힌트가 있고 물이 잠겨있는 곳만 피하면 된다. 물이 잠겨있는 곳을 제외하고 나머지 공간에 도착하면 반대로 위쪽과 왼쪽의 데이터를 가져와서 추가로 더해주면서 도착지까지 이동.

마지막에 효율성이 전부 틀려서 왜인가 했는데 나눠줘야 하는 숫자로 안 나눠줌

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