[BOJ] 1010번 : 다리 놓기

🔒 문제

⌨ 입력

🖨 출력

📚 예제

📌 풀이

이 문제는 조합을 사용해서 풀었다.

고등학교 확률과 통계 조합 단원에서, 집합 X에서 집합 Y로의 함수를 정의 할 때 조건 x1 < x2 이면, f(x1) < f(x2)를 만족하는 함수의 개수를 구하는 문제가 있다.

이 다리 놓기 문제는 다리 끼리 겹쳐지는 상황이 생기면 안되기 때문에 위의 그림에 적어놓은 것 처럼 저 조건을 사용해서 조합으로 풀 수 있다.

🔑 python 코드

#다리 놓기
import sys
input = sys.stdin.readline

T = int(input()) 
arr = [[int(i) for i in input().split()]for _ in range(T)]

#조합
def nCr(n, m):
    ans = 1
    d = 1
    for i in range(n):
        ans *= (m - i) #nPr
        d *= (i + 1) # r!
    return int(ans/d)

for i in range(T):
    print(nCr(arr[i][0], arr[i][1]))