[프로그래머스] 등굣길

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

코딩테스트 연습 - 등굣길

 

풀이

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

    for a,b in puddles:
        map[b][a]=-1

    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1:
                map[i][j]=1
            else:
                if map[i][j]==-1:
                    continue
                if map[i-1][j]==-1:
                    map[i][j]=map[i][j-1]
                elif map[i][j-1]==-1:
                    map[i][j]=map[i-1][j]
                elif map[i-1][j]==-1 and map[i][j-1]==-1:
                    continue
                else:
                    map[i][j]=(map[i-1][j]+map[i][j-1]) % 1000000007

    return map[n][m]

 

문제자체는 어렵지 않은데, puddles안에 들어있는 행렬이 반대로 되어있다는 점이랑 1,000,000,007로 나누는 것을 더할때 해야 효율성을 맞출 수 있다는 점이 함정이었다..