반응형
2407
-
BOJ) 조합 (2407 번)알고리즘/백준 2021. 2. 3. 17:43
조합 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 수학의 조합(Combination)을 구현하는 문제다. 조합 자체는 여러 방법으로 구할 수 있지만, 반복문을 통해 풀기로 했다. 그래서 combination을 직접 몇 개 써보면서 규칙을 찾았다. nCm => n! / ((n - m)! * m!) 이라는 공식이 있는데, 이를 약분하면 nCm => (n*n-1*... *n-m+1) / (m*m-1*...*1) 라는 식이 나온다. n =10인 경우를 살펴보자 N M 식 값 10 0 10! / ( (10 -0)! * 0! ) => 10! / 10! 1 10 1 10! / ( (10-1)! * 1! ) => 10! / 9! => ..