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

Python3, 동적 프로그래밍

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• 이중 반복문으로 (1,1)에서 (m,n)까지 반복
• 중간에 웅덩이(puddles)가 되면 카운트하지 않음. 지나갈 수도 없음.
• 움직일 때마다 +1 씩 카운트
• 카운트 리턴

주요 포인트

동적 프로그래밍 dp 사용

1, 1 부터 시작하는게 꼬이지 않도록 0을 임의로 만들어줌

인덱스 0은 사용하진 않지만 헷갈리지 않도록 만든 것
dp = [[0] * (m+1) for i in range(n+1)]
dp[1][1] = 1
print(dp)
=> [[0, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

i, j가 바껴 있음

dp[i][j] = dp[i-1][j] + dp[i][j-1]
새로 값을 넣을 칸 = 바로 위 칸까지의 경로 수 + 바로 왼쪽 칸까지의 경로 수
우리는 아래, 오른쪽만 이동해야 하므로 i, j를 바꿔주기

최종 코드

def solution(m, n, puddles):
    dp = [[0] * (m+1) for i in range(n+1)]
    dp[1][1] = 1
    
    # 웅덩이가 있는 곳은 -1
    for i, j in puddles:
        # i, j가 바껴 있음
        dp[j][i] = -1
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 웅덩이를 만나면
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            
            dp[i][j] += (dp[i-1][j] + dp[i][j-1]) % 1000000007
                
    return dp[n][m]