프로그래머스 - 등굣길

문제 설명

제한사항 및 입출력

풀이

정말 정석적인 DP 문제이다. 추가적으로 가지 못하는 타일만 고려해주면 된다.

 

dp[i][j] = [0, 0]에서 [i, j]까지 도달할 수 있는 방법의 수

내 코드

MOD = 10**9 + 7

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]
    for x, y in puddles:
        dp[y-1][x-1] = -1
        
    for i in range(m):
        if dp[0][i] == -1: break
        dp[0][i] = 1
    for i in range(n):
        if dp[i][0] == -1: break
        dp[i][0] = 1
    
    for i in range(1, n):
        for j in range(1, m):
            if dp[i][j] == -1: continue
            
            dp[i][j] = max(dp[i-1][j], 0) + max(dp[i][j-1], 0)
    
    return dp[-1][-1] % MOD

 

먼저 첫 번째 행과 열을 1로 초기화해주면서 중간에 가지 못하는 타일을 만나면 중단해주었다.

가지 못하는 타일을 -1로 초기화해주었기 때문에 이후 0과 비교해주면서 상태전이해주었다.

 

시간 복잡도: O(n*m) - 모든 격자 탐색

고찰

1차원 dp로 압축할 수 있다. 배낭문제도 그렇고 dp 문제들은 차원을 줄이면서 최적화하는게 재밌는 것 같다. 시간 복잡도는 동일하지만 공간 복잡도가 줄었다.

 

dp 테이블 정의는 다음과 같다.

dp[x] = 현재 y행에서 [x, y]까지 오는 경우의 수

 

이중 for문에서 바깥쪽 반복문은 위에서 아래로 한 줄씩 내려오는 반복이다. [x, y]를 처리할 때 dp[x]에는 위 칸까지의 경로 수가 저장되어있고, dp[x-1]에는 왼쪽 칸까지의 경로 수가 저장되어 있다.

MOD = 10**9 + 7

def solution(m, n, puddles):
    blocked = {(x - 1, y - 1) for x, y in puddles}

    dp = [0] * m
    dp[0] = 1

    for y in range(n):
        for x in range(m):
            if (x, y) in blocked:
                dp[x] = 0
            elif x > 0:
                dp[x] = (dp[x] + dp[x - 1]) % MOD
            # x == 0이면 위에서 내려오는 값(dp[0])만 유지

    return dp[-1] % MOD