[Python] 백준2407 조합

06 Feb 2023 in Study on Algorithm

백준2407 조합 링크

문제

예제 입력

---

코드

N, M = map(int, input().split())

n = 1
r = 0
k = 0
for i in range(1, N+1):
    n *= i
    if i == M:
        r = n
    if i == (N-M):
        k = n
# nCr = n!/r!(n-r)!
print(n//(r*k))

설명

파이썬을 통해서 사용자로부터 입력받아 조합의 수학식을 사용하여 조합를 구현했습니다.

---

정리

# 순열 nPr = n!/(n-r)! => list(permutations(arr, r))
from itertools import permutations
# 조합 nCr = n!/r!(n-r)! => list(combinations(arr, r))
from itertools import combinations
# 중복순열 nㅠr = n^r => list(product(arr, repeat=m))
from itertools import product
# 중복조합 nHr = (n+r-1)Cr => list(combinations_with_replacement(arr, r))
from itertools import combinations_with_replacement

n, m = map(int, input().split())
arr = [ i+1 for i in range(n) ]
res = list(combinations(arr, m))
print(len(res))

# 순열과 조합
from math import perm, comb
print(comb(n, m))

# dp알고리즘
dp=[1]*101
for i in range(1, 101):
    dp[i]=i*dp[i-1]

그 외에도 순열과 조합에 대한 함수를 갖는 라이브러리나 dp알고리즘으로 해결할 수 있습니다.

---

결과