[프로그래머스-Lv3] 등굣길 / Python

코딩테스트 연습 - 등굣길

import sys

input = sys.stdin.readline

m, n = map(int, input().split())
puddles = [list(map(int, input().split())) for _ in range(int(input()))]


def solution(m, n, puddles):
    d = [[0] * (m + 1) for _ in range(n + 1)]
    d[1][1] = 1

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

    return d[-1][-1] % 1000000007


print(solution(m, n, puddles))

 

해설

dp로 해결할 수 있는 문제다. 이 문제에서 사용하는 좌표는 우리가 기존에 사용하던 좌표와는 반대라는 걸 생각해야 한다.

d 리스트의 길이를 m+1 by n+1로, 모든 값은 0으로 초기화하고, (1, 1)은 1로 초기화를 해준다.

 

현재 좌표에서 위와 왼쪽의 경우의 수를 합한 값이 현재 좌표까지 오는 경우의 수가 된다.

좌표가 반대이기 때문에 [j, i]가 우물이 있는 좌표라면 그대로 0으로 놔둔다.