[백준 1010/javascript] 다리 놓기

경우의 수는 너무 많을것 같으니 알고리즘을 생각해봤다

결국은 오른쪽 전체 중에 오른쪽 - 왼쪽 사이트 만큼. 즉 선택되지 않은 것들의 경우의 수를 구하면 되는 문제였다

백트래킹을 쓰려다 머리만 아파지고 콤비네이션(조합) 을 구현해서 풀었다

dp 로도 방법이 있다는데... 굳이 안써도 간단하게도 풀린다

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

let input = [];

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (inp) => {
  inp.shift();
  for (el of inp) {
    let [n, m] = el.split(" ").map((el) => Number(el));

    let nn = m - n;
    let ans = BigInt(1);

    if (2 * n > m) {
      n = m - n;
    }
    for (let i = 0; i < n; i++) {
      ans *= BigInt(m - i);
    }
    for (let i = 1; i <= n; i++) {
      ans /= BigInt(i);
    }
    console.log(Number(ans));
  }
};