[프로그래머스] 파이썬 _ 등굣길

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

코딩테스트 연습 - 등굣길

 

문제유형 : DP

 

문제풀이 :

• 특정 좌표가 웅덩이에 포함되어있는지 확인할때 주어진 좌표는 행,열이 바뀌어잇기때문에 i,j가 아니라 j,i로 확인해줘야했다.
• 점화식 :    S[i][j] = S[i-1][j] + S[j-1][i]
  • 이때 j,i가 puddles에 포함되어있다면 위 점화식을 수행하지 않고 0으로 바꿔주고 넘어간다.

정답코드 :

def solution(m, n, puddles):
    answer = 0
    #S[i][j] = S[i-1][j] + S[j-1][i]
    #0번째 행과 열을 사용하지 않는다. 
    S = [ [0] * (m+1)  for _ in range(n+1) ] 
    S[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 [j,i] in puddles:
                
                S[i][j] = 0
            else:
                S[i][j] = S[i-1][j] + S[i][j-1]
    #print(S)      
    return S[n][m] % 1000000007