[Python] BOJ 1010 다리놓기

출처 : 백준

 

이 문제는 복잡하게 생각하면 절대로 못 푸는 문제다. 간단하게 강 동쪽 사이트에서 강 서쪽 사이트 개수를 뽑는 조합을 생각하면 된다. 조합인 이유는 문제에서도 나와있다시피 다리를 교차해서 놓을 수 없다. 

 

예를 들어 N=2, M=5라고 할 때, M으로 연결할 수 있는 사이트 N개를 뽑는 조합과 같은데 

 

좌측 그림 [1], 우츨 그림 [2]

다섯 개 중에 두개를 뽑는 조합의 수는 그림[1]의 경우와 그림 [2]의 경우가 같은 경우이기 때문에 자연스럽게 다리가 교차되는 것의 경우의 수는 빠지게 된다. 

 

자바로 이 문제를 풀면 오버플로우 문제로 인해 복잡하게 동적계획법, 조합 이론 등을 사용해야 하지만 파이썬은 앞선 포스팅에서도 다뤘다시피 오버플로우 문제가 발생하지 않기 때문에 파이썬으로 구현하면 다음과 같다.

 

def fact2(n,m):
    sum = n
    for i in range(m-1):
        n -= 1
        sum *= n
    return sum

def fact1(n):
    sum = 1
    for i in range(1,n+1):
        sum *= i
    return sum

n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    print(fact2(b,a)//fact1(a))

 

fact2는 분자를 의미하는데 5C2의 경우 분자는 5 * 4이고 분모는 2 * 1이다. 이를 그대로 구현한 것이다.