[다이나믹] BOJ#1010 - 다리 놓기

[ye-yo]

⚠️ 나의 풀이

❗️ 오답 원인 분석

• 조합을 사용해야 한다는 걸 바로 떠올리지 못함.
• 팩토리얼을 사용해야 한다는 걸 깨달았지만 적용을 못함.

🔑 풀이 핵심

• M개 중에서 N개의 정점 선택 > M개 중 N개를 고르는 경우의 수 = 조합
• 조합식 = nCr = n!/r!(n-r)!;

*이항정리 적용하면 아래와 같이 계산도 가능

int r= 1;
for(int i = M; i > M - N; i--){
     result *= i;
     result /= r++;
}

예시)

5x4x3          5x4x3x2x1          5!
-------   =  -------------  =  ------- 
1x2x3         (3x2x1)(2x1)     3!(5-3)!