Mini
1010번 : 다리 놓기 본문
https://www.acmicpc.net/problem/1010
1010번: 다리 놓기
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
www.acmicpc.net
* 문제
N개 --- M개 도시
제한: 다리 겹치기X
ex) 5----3
1,3,5 3,5,1 5,3,1 이 같음->순서없음->조합=mCn
*시간 : 0.5초
1초->1억회;
0.5초->5천만 -> 67893915->0.67초 시간초과 (-) -> 수학식필요
nCr=n!/r!(n-r)! = n(n-1)(n-2)...(1) / r(r-1)(r-2)....(1) * (n-r)(n-r-1)...(1)
=n부터 1씩 줄어들면서 r개를 곱합/1부터 1씩 늘어나면서 r 개를 곱함
mCn=m부터 1씩줄어들며 n개곱합 / 1부터 1씩 늘어나며 n개 곱함
=*(M-N--) / (0~N++)
ex)5C2= 5*4/1*2
ex2)6C3=6*5*4/1*2*3
for(int j = 0; j < N; j++) {
result *= (M - j);
result /= (j + 1);
}