백준 1010번 : 다리 놓기 - Javascript

백준 1010번 : 다리 놓기 - 자바스크립트

자료 구조

• a1
  • 타입 : 정수
  • 저장 데이터 : 서쪽사이트 개수
• a2
  • 타입 : 정수
  • 저장 데이터 : 동쪽사이트 개수

풀이 과정

1. a2에서 a1을 겹치지 않게 뽑을 수 있는 경우의 수를 구하는 문제이다. 

2. Combination 기법을 활용했다. nCm을 연산하면 m개의 자료에서 겹치지 않게 n개의 자료를 뽑을 수 있다.

3. Combination을 구현하기 하기 위해, 먼저 재귀를 이용해 Factorial 함수를 만들어 준다

4. Factorial함수를 중첩하여, Combination 함수를 구현한다.

5. Combination(a1,a2) 를 연산해 a2에서 a1을 겹치지 않게 뽑을 수 있는 경우의수를 구한다.

코드 구현

사용 언어 : 자바스크립트

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const factorial = (n) => {
  if (n === 1) return 1;
  return n * factorial(n - 1);
};
const Combination = (n1, n2) => {
  return factorial(n2) / (factorial(n1) * factorial(n2 - n1));
};
let count = 0;
let input = [];
rl.on("line", function (line) {
  if (!count) {
    count = Number(line);
  } else {
    input.push(line);
    if (input.length === count) {
      rl.close();
    }
  }
}).on("close", function () {
  input.forEach((el) => {
    let [a1, a2] = el.split(" ").map((e) => parseInt(e));
    a1 === a2 ? console.log(1) : console.log(parseInt(Combination(a1, a2) + 0.5));
  });
  process.exit();
});