[수학/DP] 백준 2407 조합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2407번: 조합

 

 

 

2. 문제 풀이

 Comb(n, m)의 값을 구하는 문제입니다.

 

from math import comb
n, m = map(int, input().split())
print(comb(n, m))

 단순히 라이브러리를 이용하면, 쉽게 풀이하실 수 있습니다. 다만 직접 구현하고 싶다면, 동적계획법을 이용해야 합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 점화식을 찾고, 항(term)을 메모해서 불러오는 동적계획법을 사용해야 시간초과를 피할 수 있습니다.

 

 조합(Combination)의 정의를 먼저 살펴보면 위와 같이, 팩토리얼이 '중복'해서 사용됩니다. n! 계산이 끝나면, r!과 (n-r)!는 불러와서 사용할 수 있죠. 따라서 DP를 이용한 팩토리얼 함수만 구현해주면 됩니다.

 

 

파스칼의 상각형 공식

 두번째 점화식은 '파스칼의 삼각형 공식'을 이용한 방법입니다. 캐시에 n과 r의 조합값을 저장하고 불러와서 사용합니다.

 

 

 

3. 코드

n, m = list(map(int, input().split()))
cache = [[-1 for j in range(m + 1)] for i in range(n + 1)]

#동적계획법
def nCr(n, r):
    #조합값이 1인 경우
    if n == 1:
        return 1
    elif n == r or r == 0:
        return 1

    #직접 계산
    else:
        if cache[n][r] == -1:
            cache[n][r] = nCr(n - 1, r) + nCr(n - 1, r - 1)
        return cache[n][r]

#출력
print(nCr(n, m))