[python] 백준 1010 : 다리 놓기

입력예시를 보면 2,2 →2 (끄덕끄덕) 1,5 → 5(끄덕끄덕) 13,29 → 67863915 (???????)

경우의 수를 직접 손으로 그려가며 따지다가 살짝 당황했습니다. 근데 생각해봅시다. 13개의 다리중 1번다리가 강건너 29개의 다리중 한개를 선택하면? 강건너에 남은건 1번다리가 선택한것을 제외한 28개의 다리겠지요. 2번다리가 이 28개의 다리중에 한개를 또 선택합니다. 3번다리는? 1,2번이 고르고 남은 27개의 다리중 한개를 선택할겁니다. 이게 반복되면 결국 경우의수는 29!/(29-13)! 이 되겠죠. 

근데 조건이 있습니다. 다리끼리는 서로 겹치면 안된다네요? 위의 계산에선 다리가 겹치는것도 포함이니 제외시켜줘야 합니다. 

숫자는 그냥 다리번호입니다. 강 서쪽과 동쪽 다리의 번호매칭이 같더라도 왼쪽은 되고 오른쪽은 안됩니다. 그럼 숫자 매칭하는 경우만 따져주면 되는거네요. 다리의 갯수는 서쪽 사이트의 갯수 n개만큼 지어지므로, 동쪽에 있는 사이트 m개중 n개를 뽑으면됩니다. 뽑았을때의 순서는 무시하고 숫자(다리번호)의 구성만 중요합니다. 뽑힌 숫자들을 오름차순으로 서쪽의 1번다리부터 할당하면 되니까요.

예를들어 서쪽엔 3개의 사이트, 동쪽엔 5개의 사이트가 있다고하면 동쪽 5개의 사이트(다리번호 1~5)중에서 3개만 뽑읍시다. 뽑았을때 4,1,5가 뽑힌경우 이 숫자구성을 작은값부터 서쪽 사이트 1번다리에 할당하면됩니다. 그렇다면? 나중에 만약구성이같은 5,4,1이 뽑혔을땐 중복되는 경우겠지요. 어차피 작은값부터 할당하면 1,4,5가 되니까요

 

m개에서 n개만큼 순서를 고려하지않고 뽑는 경우... 바로 조합(Combination)입니다. 고등수학 확률과통계 1단원에 나올텐데요(아마? 수능본지 5년이 넘어가니 가물가물하네요.. like 가물치,,,..,,) 위의 문제의경우 동쪽 m개 사이트에서 n개만큼 순서를 고려하지않고 뽑아야하므로 mCn이겠네요

mCn은 m!/(m-n)!n! 이므로 전에 풀었던 팩토리얼을 잘 이용하면 간단히 풀립니다.

 

def fact(k):
    if k<=1:
        return 1
    else:
        return k*fact(k-1)

def combination(m,n):
    X=fact(m)
    Y=fact(n)*fact(m-n)

    return X/Y


T=int(input())

for _ in range(T):
    n,m=map(int,input().split())

    print(int(combination(m,n)))

팩토리얼 함수를 생성한후 조합 함수에서 잘 써줍시다. 팩토리얼은 재귀호출을 이용하는 대표적 예시인데 자세한내용은 티스토리 사이버노가다 인력사무소 글에 팩토리얼을 잘 설명해놓은 글이 있읍니다 봐주신다면 감사할거같은데,,,~

조합을 생각했다면 금방 해결할수있었던 문제입니다. 다행히 간단히 풀려서 글이 길지않네요 모두 Adios.