[Python] 프로그래머스: 도둑질

문제

코딩테스트 연습 - 도둑질

---

풀이

a.  접근법

[0,0] ~ [m, n]까지의 최단 거리 경로의 수 구하는 방법

최단 거리 경로의 수

b. 실패

해당 index에 대하여 모든 경로의 수를 먼저 계산한 뒤, 갈 수 없는 경로의 수를 계산하여 제하는 방법 -> 효율성, 정확성 모두 실패
  * 시간복잡도 O(N^3)
  그림 때문에 m, n이 너무 헷갈렸다ㅠㅠㅠ

def get_shortest_path(start_y, start_x, end_y, end_x):
    dp0 = [[1] * (end_y-start_y) for _ in range(end_x-start_x)]
    for i in range(1, end_x - start_x):
        for j in range(1, end_y - start_y):
            dp0[i][j] = dp0[i - 1][j] + dp0[i][j - 1]

    return dp0[end_x-start_x-1][end_y-start_y-1]

def solution(m, n, puddles):
    answer = get_shortest_path(0, 0, m, n) % 1000000007
    for val in puddles:
        a = get_shortest_path(0, 0, val[1], val[0])
        b = get_shortest_path(val[1], val[0], m + 1, n + 1)
        answer -= (a*b)
        answer %= 1000000007

    return answer

 

 

c.  최종 풀이

갈 수 없는 길을 block 처리한 뒤, [m+1, n+1]까지 이동하며 그때 그때 이동 가능한 최단 거리 경로의 수를 계산하도록 단순화
  * 시간복잡도 O(N^2)

def solution(m, n, puddles):
    dp = [[0] * (n+1) for _ in range(m+1)]
    for val in puddles:
        dp[val[0]][val[1]] = -1     # 갈 수 없는 길을 block 처리

    dp[1][0] = 1                    # 시작값 지정
    for i in range(1, m+1):
        for j in range(1, n+1):
            if dp[i][j] == -1:
                dp[i][j] = 0
            else:       # 갈 수 있는 길인 경우, 최단 경로의 경우의 수 계산
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007

    return dp[m][n]