(파이썬) 등굣길 - 동적계획법

컴닥 2019. 9. 24. 22:40

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =

programmers.co.kr

def solution(m, n, puddles):
    arr = [[0 for _ in range(m)] for _ in range(n)]  # 경로를 담을 배열을 만듭니다. 
    arr[0][0] = 1  # 집의 위치에는 1이 들어가야 합니다. 
    for x, y in puddles:  # 웅덩이를 반영합니다.
        arr[y - 1][x - 1] = None
    for y in range(n):
        for x in range(m):
            if arr[y][x] is not None:  # 좌표 상 위의 경우의 수와 좌의 경우의 수의 합이 됩니다.
                arr[y][x] += 0 if arr[y - 1][x] is None else arr[y - 1][x]
                arr[y][x] += 0 if arr[y][x - 1] is None else arr[y][x - 1]
    return arr[-1][-1] % 1000000007

정확성  테스트
테스트 1 〉	통과 (0.01ms, 9.52MB)
테스트 2 〉	통과 (0.03ms, 9.59MB)
테스트 3 〉	통과 (0.04ms, 9.57MB)
테스트 4 〉	통과 (0.06ms, 9.51MB)
테스트 5 〉	통과 (0.13ms, 9.6MB)
테스트 6 〉	통과 (0.09ms, 9.45MB)
테스트 7 〉	통과 (0.09ms, 9.37MB)
테스트 8 〉	통과 (0.20ms, 9.62MB)
테스트 9 〉	통과 (0.10ms, 9.51MB)
테스트 10 〉	통과 (0.04ms, 9.62MB)
효율성  테스트
테스트 1 〉	통과 (5.59ms, 9.75MB)
테스트 2 〉	통과 (2.04ms, 9.55MB)
테스트 3 〉	통과 (2.44ms, 9.73MB)
테스트 4 〉	통과 (3.32ms, 9.75MB)
테스트 5 〉	통과 (2.86ms, 9.62MB)
테스트 6 〉	통과 (4.43ms, 9.76MB)
테스트 7 〉	통과 (2.42ms, 9.62MB)
테스트 8 〉	통과 (3.47ms, 9.84MB)
테스트 9 〉	통과 (3.59ms, 9.81MB)
테스트 10 〉	통과 (3.52ms, 9.59MB)

전형적인 동적계획법 문제입니다.
경로를 담는 배열을 만들고, 배열에 경우의 수를 넣고, 합하면 됩니다.