[Python] 1010번 : 다리 놓기

 

문제 설명 3줄 요약

 

1. 강 주변에는 다리를 놓기에 적합한 '사이트'가 있다.

2. 재원이는 강 서쪽 사이트(N개)와 동쪽 사이트(M개)를 이어주는 다리를 놓는다. (N <= M)

3. 한 사이트 당 한 개의 다리만 연결, 최대한 많은 다리(N개)를 지을 수 있는 경우의 수 구하자!

※ 다리끼리 겹치기 불가

 

 

문제를 읽자마자 든 생각,

수학 시간에 자주 들었던 문제!

 

N개의  빨간 공과 M개의 파란 공을 잇는 경우의 수는?

바로 조합(Combination) 문제 

 

순열과 조합의 차이는 '순서의 고려' 이지만

다리를 놓는 경우에서 순서는 상관이 없다.

 

https://coding-factory.tistory.com/606

 

여기서 느낌표(!) 는 팩토리얼,

 

https://coding-factory.tistory.com/606

 

따라서 팩토리얼만 함수로 구현해주고

조합 계산을 해주면

 

# T = 테스트 케이스 수 입력 받기
T = int(input())

# 다리를 놓을 수 있는 경우의 수는 순열의 조합(combination)
# 재귀 함수로 팩토리얼 함수 구현
def combination(number):
    if number > 1:
        return number * combination(number-1)
    return 1

if __name__ == '__main__':
    for count in range(T):
        # N개의 사이트, M개의 사이트 입력
        N,M = map(int, input().split())
        
        # 순열 조합 
        answer = combination(M)/(combination(N)*combination(M-N))
        print(int(answer))

 

끝!