[코딩테스트] 프로그래머스 - 등굣길

1. 아이디어 

▪ dp 알고리즘으로 구현 

▪ (i,j) 좌표로 가는 경로의 수는 다음의 점화식을 따름 -> dp[j][i] = dp[j-1][i] + dp[j][i-1]

▪ 경로의 수를 저장할 dp 리스트 0으로 초기화, 시작점인 (1,1)은 1로 초기화

▪ 2중 for문 돌면서 경로의 수 리스트 채우기 

   - (1,1)인 경우 skip

   - (i,j)가 물에 잠긴 경우 해당 좌표로 가는 경로의 수는 0 

   - (i,j)로 가는 경로의 수는 (i-1,j)로 가는 경로의 수와 (i,j-1)로 가는 경로의 수를 더한 값에 % 1000000007

▪ dp의 마지막 행, 마지막 열 값 return 

2. 시간복잡도

▪ O(n*m)

3. 변수

▪ 경로의 수를 저장할 리스트: int[][]

Code

def solution(m, n, puddles):
    answer = 0
    
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[1][1] = 1
    
    for j in range(1,n+1):
        for i in range(1,m+1):
            if i == 1 and j == 1: 
                continue
            if [i,j] in puddles:
                dp[j][i] = 0 
            else:
                dp[j][i] = (dp[j-1][i] + dp[j][i-1]) % 1000000007
            
    answer = dp[n][m] 
    
    return answer

프로그래머스