[알고리즘 문제] Combinational pascal (Python / 파이썬)

문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.
n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.  

입력

첫째 줄에 정수 n, m(0 ≤ m ≤ n ≤ 30)이 들어온다.

출력

첫째 줄에 nCm의 값을 출력한다.

---

문제 풀이 

이번 문제는 조합을 구하는 문제입니다. 

두 가지 방법으로 조합을 구해보았습니다. 

먼저 파스칼의 삼각형으로 조합을 구할 수 있습니다.

파스칼의 삼각형은 아래와 같이 위의 두 수의 합으로 아래의 수를 구성하는 삼각형 입니다.

파스칼의 삼각형은 n번째 줄의 m번째 원소가 nCm을 만족시킵니다. 

따라서 파스칼의 삼각형을 2차원 배열로 구현해 조합을 구할 수 있습니다. 

 

두 번째 방법은 조합을 구하는 식을 이용하는 것 입니다. 

조합을 계산하는 식은 아래와 같습니다.

이 공식을 이용해 조합을 구할 수도 있습니다.

---

My Code 1 - 파스칼의 삼각형 이용

n, m = map(int,input().split()) 

pascal = [[1] * (n + 1) for _ in range(n + 1)]

# 파스칼의 삼각형
for i in range(2, n + 1):
    for j in range(1, i):
        pascal[i][j] = pascal[i - 1][j] + pascal[i - 1][j - 1]

# nCm 값 출력
print(pascal[n][m])

My Code 2 - 조합 공식 이용

n, m = map(int,input().split()) 

result = 1
for i in range(1, m + 1):
    result *= (n - m) + i # n! / (n-m)! 계산
    result //= i          # m! 나눠줌

print(result)