[백준/Python] 1010번: 다리 놓기

문제

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

---

문제 요약

강 서쪽에 N개, 동족에 M개의 사이트가 존재할 때 서로 겹치지 않게 다리를 지을 수 있는 경우의 수를 출력한다.
 
+ 사이트란 강 주변에서 다리를 짓기에 적합한 곳이다.

+ 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.

---

코드

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    # N은 서쪽의 사이트 개수, M은 동쪽 사이트 개수

    small = min(N, M)
    big = max(N, M)

    res = 1

    # small C big의 분자 계산 
    for i in range (big, big - small, -1):
        res *= i

    # small C big의 분모 계산
    for i in range(1, small + 1):
        res //= i

    print(res)

---

코드 설명

다리를 지을 수 있는 경우의 수는 사이트 개수가 더 많은 쪽에서 적은 쪽 의 개수만큼 고를 수 있는 경우의 수이다.
(고르기만 하면 차례대로 연결시키면 된다.)
 
즉 Combination 계산이 필요하다.
 
+ 리스트를 만들어 완전 탐색이나, combination tool을 이용하면 시간 초과 문제가 발생한다.
=> 따라서 리스트를 만들어 경우의 수를 일일이 구하는 것이 아니라 개수만 구해야한다.
 
 
1. min, max 함수를 통해 더 큰 값과 작은 값을 고른다.
 
2. combination 계산 식의 분자를 계산한다.
 
3. combination 계산 식의 분모를 계산한다.
 
4. 값을 출력한다.