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

풀이 1

보자마자 생각나는 것..

확통에서 풀던 최단거리 경우의 수 문제 (같은 것이 있는 순열)

 

그 방식대로 풀이해보자

from math import factorial
def solution(m, n, puddles):
    def shortcut(m, n):
        return int(factorial(m+n) / (factorial(m) * factorial(n)))

    answer = shortcut(m-1, n-1)

    for li in puddles:
        answer -= shortcut(m - li[0], n - li[1]) * shortcut(li[0]-1, li[1]-1)

    return answer

 

이러면 문제가..

puddles의 개수가 2개를 넘어가면

두 웅덩이를 모두 지나는 경우의 수를 여러 번 빼 주게 되어 다 처리해야 함.

귀찮으니까 다른 방법으로 ㄱ

 

풀이 2

Top-Down 방식으로 해봄

def solution(m, n, puddles):
    def dp(m, n):
        if m == 1 and n == 1:
            return 1
        elif [m, n] in puddles:
            return 0
        elif m == 1:
            return dp(m, n-1)
        elif n == 1:
            return dp(m-1, n)
        else:
            return dp(m-1, n) + dp(m, n-1)

    return dp(m, n)

시간초과남..

 

풀이 3

Bottom-Up 방식으로 가보자고

주의할 점은.. 1000000007 로 결과값을 나눠줘야 한다는 것과

행렬이 뒤집어져 있다는 사실..

def solution(m, n, puddles):
    puddles = list(map(lambda x: [x[1], x[0]], puddles))
    dp = [[0]*(m+1)]*(n+1)
    dp[1][1] = 1

    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            elif [i, j] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[n][m] % 1000000007