[javascript] 백준 11050번 이항 계수 1

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

11050번: 이항 계수 1

 

 

 

문제

 

 

 

👀 풀이

정수론 및 조합론 문제인 이항 계수 1.

이항계수는 말 그대로 '두 개의 항(이항)을 전개하여 계수로 나타낸 것'이다.

쉽게 말하면, (a + b)^n 을 전개하였을 때의 계수를 의미한다는 것.

 

이러한 이항계수를 구하는 방법은 다음과 같다.

이항계수를 구하는 점화식

우리 문제와 조건이 같은 첫번째의 n!/(k!*(n-k)!)를 사용하면 되겠다!

단 주의할점이 있는데 nCk에서 k가 0일때는 1을 반환하므로 k가 0이나 1일때 1을 반환하도록 해주어야한다.

 

예제를 들어 설명을 하자면,

5 2 //N(n) K(k)

5! = 5 * 4 * 3 * 2 * 1

2!(5-2)! = 2!3! = 2 * 1 * (3 * 2 * 1)

 

계산하면  5 * 2 이므로 예제 출력값 10이 나온다!

 

 

 

이러한 nCk를 구하는 또 다른 방식이 있다! 바로 nPk / k!

nPk = n(n-1)…(n-k+1) (k≤n)을 의미한다. 즉 n부터 시작해 1씩 줄여나가며 (n-k+1)인 수까지를 곱하는 것!

 

예제로 또 한 번 설명을 하자면,

5P2 = 5 * 4

2! = 2 * 1

 

계산하면 마찬가지로 예제 출력값이 10이 나온다.

 

2번이 더 간단하고, 알고리즘 계산 속도도 더 빠르다니까 두 번째 방식을 쓰는 걸 추천!

 

 

 

💡 코드

첫 번째 공식을 이용하는 경우 [ n!/(k!*(n-k)!) ]

const fs = require('fs');
const [N, K] = fs.readFileSync("./dev/stdin").toString().trim().split(" ").map(v => +v);

let n = 1;
let r = 1;
let n_r = 1;

// n! 
for (let i = 1; i <= N; i++) {
  n *= i; // n = n * i ==> n = 1 * 1, n = 1 * 2, n = 1 * 3, ... n = 1 * 5
}

// k!
for (let i = 1; i <= K; i++) {
  r *= i
}

// (n-k)!
for (let i = 1; i <= N - K; i++) {
  n_r *= i
}

console.log(n / (r * n_r));

 

두 번째 공식을 이용한 경우  [ nPk / k! ]

const fs = require('fs');
const [N, K] = fs.readFileSync("./dev/stdin").toString().trim().split(" ").map(v => +v);

let n = 1;
let r = 1;

// nPk 구하기
for (let i = N-K+1; i <= N; i++) {
  n *= i;
}

// k!
for (let i = 1; i <= K; i++) {
  r *= i
}

console.log(n / r);

 

 

📍 참고

https://lhoiktiv.tistory.com/184

Node.js) 백준 11050번 : 이항계수 1