문제

입력

출력

예제 입출력

풀이

일단 간단하게 생각했다. N개의 사이트에서 M개의 사이트로 가능한 모둔 경우의 수를 구하는 문제이다. 몇가지 조건이 존재한다.

• $N \leqq M$ 이기 때문에 도착지가 더 적은 경우는 없다.
• N이 0보다 크기 때문에, 출발지가 없는 경우는 없다.
• 다리를 겹쳐둘 수 없고, 한 포인트당 한개의 다리를 둘 수 있다.

이를 생각했을때, 조합(Combination)인 것을 알 수 있다. $M$개의 가능한 도착지에서 $N$의 출발지로부터의 도착지점을 순서없이 선택하는 경우의 수와 같다. 이에, 조합식을 위해서 factorial 함수를 구현했다.

# 다리 놓기
T=int(input())

def factorial(N):
    if N==1 or N==0:
        return 1
    return N*factorial(N-1)


for _ in range(T):
    N,M=map(int,input().split())
    print(factorial(M)//(factorial(M-N)*factorial(N)))

하지만...순열 조합 자체를 math 라이브러리를 통해 사용 가능하다.

# 다리 놓기
import math
T=int(input())

for _ in range(T):
    N,M=map(int,input().split())
    print(math.comb(M,N))

박탈감 무엇...? DP에 해당하는 문제인데, 사실 그냥 재귀함수로 어쩌다 구현에 성공했다. 아마 N과 M의 크기가 커졌으면 시간초과나 메모리 초과가 떴을 것 같다. DP로 구현하는 방법도 따로 찾아봐야할것 같아서 찾아보니 다양한 풀이가 존재했다. 아래의 Reference에 DP를 활용한 방법으로 구현한 멋진..개발자분이 계셔서...참조링크를 달아뒀다..

Reference

https://www.acmicpc.net/problem/1010
https://kau-algorithm.tistory.com/780