✓

태그:

CLASS 4 ESSENTIAL

₁₀₀C₅₀의 값은 10³⁰보다 작습니다…!!

풀이 비스무리한거 보기

_nC_m의 값을 구하는 문제입니다. 조건에 따르면 n은 5 이상 100 이하, m은 5 이상 100 이하이되 n보다 작거나 같은 값을 가집니다. 이 문제의 최대의 출력값인 ₁₀₀C₅₀의 값은 100891344545564193334812497256으로, 10²⁹보다 크고 10³⁰보다 작습니다. C++에서 사용할 수 있는 가장 큰 정수형인 unsigned long long을 생각해보면 그 최댓값은 2⁶⁴-1로, 10¹⁹보다 약간 큽니다. 따라서, 연산 중간의 결과값이나 최종 결과값을 저장할 때에는 ull 2개를 사용하면 될 것 같습니다. 이제 조합의 값을 구하는 점화식인 $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$을 이용하여 조합의 값을 구하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-23 22:25:20

---