[프로그래머스 Lv.3] 동적계획법(Dynamic Programming - 등굣길

✨ 문제 ✨

✨ 정답 ✨

function solution(m, n, puddles) {
    let dp=Array.from({length:n+1}, ()=>new Array(m+1).fill(0));
    for (let i=1;i<=n;i++){
        for (let j=1;j<=m;j++){
            if (i===1&&j===1){
                dp[i][j]=1;
            }else{
                if (isPuddle(i, j, puddles)){
                  continue;}
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
                
            }
        }
        }
    
    
    return dp[n][m]
}

const isPuddle = (x, y, puddles) => {
  for(const puddle of puddles) {
    if(puddle[0] === y && puddle[1] === x)
      return true;
  }
  return false;
}


// 실패 코드
function solution(m, n, puddles) {
    let dp=Array.from({length:n+1}, ()=>new Array(m+1).fill(0));


    for (let i=1;i<=n;i++){
        for (let j=1;j<=m;j++){
            dp[1][1]=1;
                if (i===puddles[0][1]&&j===puddles[0][0]){
                    continue;
                }
              dp[i][j]=dp[i-1][j]+dp[i][j-1]
            }
        }
    
    
    console.log(dp)
    return dp[n][m]%1000000007
}

🧵 참고한 정답지 🧵

프로그래머스 정답지

💡💡 기억해야 할 점 💡💡

1. 왜 안되나 했는데 웅덩이가 여러개일 수도 있는 것이었다. 난 바보다.
2. 주석도 시간 초과를 일으킬 수 있다.