long long combination(int n, int r) // nCr expression { long long sum = 0; // if(n/2 < r) { // r = n-r; // } not necessary for(int i = 1; i < r; i++){ sum *= (long)n-i+1; sum /= i; } return sum; } 보통 조합/이항계수 표현을 다음과 같이 구현합니다. i를 나눴을 때 나머지가 생길 가능성은 없습니다. 그 이유는 sum은 n, n-1, n-2 ....을 차례대로 곱하고, 1, 2, 3, .... 을 차례대로 곱하는데 2를 나눌 때 항상 n, n-1 둘 중 하나에 2를 인수로 가지는 수가 무조건 존재하고, n, n-1, n-2 셋 중 하나에 3을 가지는 인수가 무조건 존재하며, 이 규칙을 i가 r이 될 때 적용하면 문제가 없기 때문입니다. 추가로 n < r일 때 그 답을 제대로 출력하지 못합니다.