[백준 1010번] DP(다이나믹 프로그래밍) - 다리 놓기

✨ 문제 ✨

✨ 정답 ✨

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n')
let T = +input[0]
input.shift();

const solution = (N, M) => {

  const dp = Array.from(Array(30), () => Array(30).fill(0));

  dp[1][1] = 1;
  dp[1][2] = 2;
  dp[1][3] = 3;
  for (let i = 1; i <= N; i++) {
    for (let k = 1; k <= M; k++) {
      if (i===k){
        dp[i][k]=1;
      }else if (i===1){
        dp[i][k]=k;
      }else{
        let temp=0;
        for (let t=1;t<k;t++){
          temp+=dp[i-1][t];
        }
        dp[i][k]=temp
      }

    }
  }
  console.log(dp[N][M])

}


for (let i = 0; i < T; i++) {
  let N = +input[i].split(' ')[0]
  let M = +input[i].split(' ')[1]
  solution(N, M)
}

🧵 참고한 정답지 🧵

https://wonyoung2257.tistory.com/39

💡💡 기억해야 할 점 💡💡

dp라고 해서 무작정 식을 적기만 하면 안 되는 것이다. 필요한 경우 케이스를 나누어 주어야 한다.