백준 1010번- '다리 놓기' (PYTHON 풀이)

문제:

 

해당 문제는 조합론과 관련된 문제이다.

설명대로 다리를 지어줄건데 여기서 중요한 포인트는 두가지가 있다. 

 

1.  한 사이트에는 한 개의 다리만 놓을 수 있다.

2. 서로 다른 다리가 겹치면 안된다.

 

해당 조건을 충족하기 위해서는 개수가 더 많은 동쪽 다리에서 서쪽 다리를 선택하면 된다. 대신 위, 아래순으로 순서대로 해야 겹치지 않는다. 결국은 순서에 무관한 조합론 공식을 쓰면 되고 이를 활용할 경우 위 조건 두가지를 충족해서 문제를 풀 수 있다.

조합론과 관련된 공식은 이항 계수 문제를 풀이했던 페이지를 참고하면 된다.

https://jyamethyst21.tistory.com/80

백준 11050번- '이항 계수 1' (PYTHON 풀이)

 

풀이:

T = int(input())

def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num

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

이항 계수 문제에서의 코드를 거의 그대로 가지고 온거라 딱히 설명할 부분은 없다. 

이 공식이 조합 공식이므로 이를 활용해서 팩토리얼 함수를 작성하고 공식에 맞게 출력하면 된다.

여기서 N은 전체 개수인 동쪽 다리의 개수를 의미하며 K는 선택하는 다리의 개수인 서쪽 다리를 의미한다.