[프로그래머스] 등굣길

문제바로가기

dp 문제이다.

def solution(m, n, puddles):
    puddles = [[j, i] for i, j in puddles]
    road = [[0 for _ in range(m+1)] for _ in range(n+1)]
    road[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 [i, j] in puddles:
                road[i][j] = 0
            else:
                road[i][j] = (road[i-1][j] + road[i][j-1]) % 1000000007
    print(road)
    return road[n][m]

제일 오래걸린 것은 puddles = [[j, i] for i, j in puddles]이다. puddles가 n,m이 아니라 m,n 순서로 되어 있어서 위치를 바꿔줘야한다. 하필 테스트 케이스가 [2,2]라서 더 알아차리기 힘들었다. 결국 검색해서 알아냄. 도대체 왜 이런 짓을 하는가... 인내심 테스트?