[알고리즘] 프로그래머스 - 등굣길

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

내 풀이

def solution(m, n, puddles):
    dp = [[0 for _ in range(m)] for _ in range(n)]
    MOD = 1000000007

    for puddle in puddles:
        dp[puddle[1]-1][puddle[0]-1] = -1

    dp[0][0] = 1
    for i in range(n):
        for j in range(m):
            if dp[i][j] == -1:
                continue
            if i-1 >=0 and dp[i-1][j] != -1:
                dp[i][j] += (dp[i-1][j] % MOD)
                dp[i][j] %= MOD
            if j-1 >= 0 and dp[i][j-1] != -1:
                dp[i][j] += (dp[i][j-1] % MOD)
                dp[i][j] %= MOD
    return dp[n-1][m-1] % MOD

오랜만에 2차원 리스트를 선언해서 잘 생각나지 않았다. 이번에 숙지해두자.

dp 문제를 오랜만에 풀어서 조금 해맸다.

이 그림을 통해서 왜 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 되는지 알 수 있다.
출처

처음에 MOD 연산을 해주는 것을 깜빡하고 냈는데 테스트 케이스는 다 통과하는데 효율성에서 다 에러가 났다. 효율성이 인풋이 커지면서 MOD 연산을 제대로 안해주니 에러가 난 것인데, 이것으로 알 수 있는 것은 효율성이 반드시 시간 복잡도에 의해 에러가 나는 것이 아닐 수도 있다는 것이다.