[알고리즘] 다리놓기 javascript

주의 !

1. 한 사이트에는 한 개의 다리만 놓일 수 있다.
2. 서로 다른 다리가 겹치면 안된다.

 

2와 4로 만들어진 예시

 

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
let T = +input[0];
let dp = new Array(31).fill(null).map(_ => new Array(31).fill(0));
function sol(N, M) {  
  for(let i=1; i<=30; i++) { // M
    for(let j=1; j<=30; j++) { // N
      if(i === j) dp[i][j] = 1;  // 입출력 예제 1 
      else if(j === 1) dp[i][j] = i;  // 입출력 예제 2
      else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; // mCn = (m-1)C(n-1) + (m-1)C(n)
    }
  }
  return dp[M][N];
}
function main() {
  let answer = '';

  for (let i = 1; i <= T; i++) {
    let [N, M] = input[i].split(' ').map(Number);
    answer += sol(N, M) + '\n';
  }

  console.log(answer.trim());
}
main();