[알고리즘/동적 계획법] 1010번 : 다리놓기 - python

링크 : https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

---

• 문제
• 소요시간:22분 12초

---

• 설계하기(접근방법) 

1. 테스트 케이스를 입력받는다

2. 알고리즘 구현

팩토리얼을 구현한다.

ex) 7개 중에 4개를 선택하여 순서와 상관없이 다리가 이어지는 조합(combination)문제다

따라서 7! / ((7-4)! *4!) 을 연산한다.

3. 답을 구현한다.

 

---

• 코드(출력)

t = int(input())


def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num


for i in range(t):
    n, m = map(int, input().split())
    ans = factorial(m) / (factorial(n) * factorial(m - n))
    print(int(ans))

---

• 얻어갈 부분

1. 팩토리얼 함수를 여러 형식으로 만들 수 있다.