[BOJ] 1010번 다리놓기 (Python)

문제

해결 방법

강의 서쪽에 있는 사이트 개수만큼 (N개)의 점을 동쪽에서 골라서 연결한다.
M개에서 순서를 고려하지 않고 N개를 고르는 것으로 mCn = m!/(m-n)!n! 이 된다.

실제 구현

방법1 - itertools

조합을 구하는 것이므로 itertools의 combination을 사용해서 구현한다.

import itertools

def solution(n, m):
    m_list = list(range(m))
    result = list(itertools.combinations(m_list, n))
    print(len(result))

단순 개수만 구하면 되는 문제이므로, 불필요한 리스트를 만들어 조합을 구하는 것은 비효율적이었다.
시간 초과도 발생하였다.

방법2 - math(factorial)

팩토리얼 계산만 하도록 파이썬의 math 모듈을 import 해서 구현한다.

import math

if __name__=='__main__':
    case = int(input())
    for _ in range(case):
        n, m = map(int, input().split())
        result = math.factorial(m)//(math.factorial(m-n) * math.factorial(n))
        print(result)

방법3 - dp

mCn = m-1Cn + m-1Cn-1 이라는 점화식을 이용한다.
n, m이 30 이하라는 조건이 있으므로 미리 dp[n][m]을 계산하고 입력에 맞게 결과를 출력한다.

dp = [[0]*30 for _ in range(30)]

for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]