.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
수학, 구현, 211102
문제
자연수 과 정수 가 주어졌을 때 이항 계수 를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 과 가 주어진다. (1 ≤ ≤ 10, 0 ≤ ≤ )
출력
를 출력한다.
예제 입력 1
5 2
Plain Text
복사
예제 출력 1
10
Plain Text
복사
My solution
이항 계수 는 잘 아는 공식으로 바꾸어 보면 을 구하라는 것이다. (여기서는 N, K)
이항 계수라는 용어보다 조합이 익숙해서 무엇인지 찾아보다가 아래의 블로그에서 많은 인사이트를 얻을 수 있었다.
결정적인 것은 이 조건을 가지고 재귀를 만들어 재귀의 탈출 조건을 정해주는 것이다.
첫번째 성질을 보면 왜 1이 되는지 궁금할 수 있다. 흰돌과 검은돌이 각각 한개씩 있는 집합이 3개가 있을 때 이 3개의 집합에서 2개의 흰돌을 뽑는 경우의 수는 결과적으로 다른 한개를 검은 돌로 뽑는 것을 강제하게 된다. 즉, 검은 돌 하나로 뽑는 경우의 수는 2개의 흰돌을 뽑도록 강제하므로 서로 조합의 대칭성에 의해서 같은 경우의 수를 갖게 된다. 이에 따라 첫번째 성질도 의 k에 0을 집어 넣은 것과 같다. n개 중에 0개를 뽑는 경우의 수는 1가지, n개 중에 n개를 뽑는 경우의 수도 1가지이다.
두번째 성질은 파스칼 삼각형으로 이해하는 것이 편하다.
이 같은 성질들로 만들어진 점화식은 다음과 같고 재귀로 구현하면 N이 1~10인 덕에 스택 오버플로우가 발생하지 않고 결과가 잘 나온다.
소스코드
function solution(i) {
const input = i.toString().trim().split(" ");
[N, K] = input;
function binomialCoefficient(n, k) {
if (n == k || k == 0) return 1;
else
return (
binomialCoefficient(n - 1, k - 1) +
binomialCoefficient(n - 1, k)
);
}
console.log(binomialCoefficient(N, K));
return binomialCoefficient(N, K);
}
test("solution", () => {
expect(solution(`5 2`)).toStrictEqual(`10`);
});
JavaScript
복사
