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

등굣길

프로그래머스

 

 

• 첫 풀이 - fail (시간초과)
  • 백트래킹 -> top-down 코드로 바꾸려고함
    
    • 어떤 점이 달라서 top-down으로 짜면 시간초과가 나는지 잘 모르겠음...
      • 5,5 /6,6/7,7/8,8 돌려보니 재귀 횟수가
      • 167
        619
        2331
        8847번이나 늘어남.....
      • 100,100 넣으면 터짐
    • 📍재귀를 사용할땐 꼭 테케 추가해서 확인해볼 것
  • 0,0부터 시작하려면 puddle도 px-1,py-1해서 저장하기

INF=1000000007
def solution(m, n, puddles):
    puddle_set = {(py, px) for px, py in puddles}

    dp = [[-1] * (m+1) for _ in range(n+1)]

    def recur(i, j):
        # 목적지에 도달하면 1개의 경로를 반환
        if i == n and j == m:
            return 1

        if i > n or j > m or (i, j) in puddle_set:
            return 0

        dp[i][j] = (recur(i + 1, j)+recur(i, j + 1)) % INF
        return dp[i][j]

    return recur(1,1)% INF

 

• 내 풀이 -success
  • bottom-up

INF=1000000007
def solution(m, n, puddles):
    puddles_set={(py,px) for px,py in puddles}
    answer = 0
    
    dp=[[0]*(m+1) for _ in range(n+1)]
    dp[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_set:
                dp[i][j]=0
                continue 
                
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%INF
            
    return (dp[n][m])%INF