알고리즘

[웅's 프로그래머스] 등굣길 - 파이썬(python) 풀이

프로그래머 웅쓰 2021. 9. 22. 18:33

이 문제를 풀 때 모두 다음과 같은 풀이 법을 떠올렸을 것이라 생각한다. 어떤 위치에 올 수 있는 경우의 수는 위쪽 위치에 올 수 있는 경우의 수와 왼쪽 위치에 올 수 있는 경우의 수를 더한 것이다. 웅덩이가 있는 부분은 in 함수를 써서 해당 위치일 경우에는 0 값을 넣어주면 간단하게 해결되는 문제이다!

그리고 나는 이러한 방식을 첫줄과 첫열에도 적용하기 위해서 (계산의 편의를 위해) 한 줄과 한 열을 더 만들었다. 한 줄씩을 더 만들고 집이 있는 곳의 값을 1로 주면 왼쪽과 위에 있는 값을 더해서 현재의 값이 나오도록 짤 수 있다.

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