문제
이항 계수 C(n, k)는 서로 다른 n개의 항목 중에서 순서와 상관없이 k개를 고르는 경우의 수입니다. 공식 n! / (k! (n − k)!)를 쓸 때 팩토리얼부터 계산하면 금방 오버플로가 납니다. 답을 한 단계씩 쌓아 가거나 파스칼의 법칙 C(n, k) = C(n − 1, k − 1) + C(n − 1, k)를 이용하세요.
binomial_coefficient(n, k) 함수를 구현하세요.
입력
n: 항목의 개수입니다.
k: 고를 개수입니다.
출력
C(n, k)를 반환합니다. k > n이면 고를 방법이 없으므로 0을 반환합니다.
제약 조건
0 ≤ n ≤ 66
0 ≤ k ≤ 100
예시
입력:
n = 5
k = 2
예상 출력:
expected = 10
입력:
long long n = 5;
long long k = 2;
예상 출력:
long long expected = 10;
입력:
long n = 5;
long k = 2;
예상 출력:
long expected = 10;
설명
5개 중에서 2개를 고르는 경우는 5 × 4 / 2 = 10가지입니다.
입력:
n = 6
k = 0
예상 출력:
expected = 1
입력:
long long n = 6;
long long k = 0;
예상 출력:
long long expected = 1;
입력:
long n = 6;
long k = 0;
예상 출력:
long expected = 1;
설명
아무것도 고르지 않는 방법은 정확히 한 가지이므로 1입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
20보다 큰 수의 팩토리얼은 64비트에 들어가지 않으므로 쓰지 마세요.
힌트 2
파스칼의 삼각형의 한 행을 오른쪽에서 왼쪽으로 제자리에서 갱신할 수 있습니다.
힌트 3
C(n, k)는 C(n, n − k)와 같고, k > n이면 0입니다.
예상 복잡도
시간 O(n · k), 추가 공간 O(k)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.