[BOJ] 다리놓기(1010) - PYTHON

강이 위에서 아래로 흐르고 서쪽, 동쪽 땅으로 구분돼있다. 서쪽과 동쪽에는 각각 다리를 놓을 수 있는 포인트들이 N, M개 있다. (M >= N) 이때 서쪽에서 동쪽으로 다리를 놓으려고 할 때 다리를 놓을 수 있는 최대 경우의 수를 찾는 문제다.

시간 복잡도: O(MN)

---

풀이과정

강의 서쪽 땅 N개의 포인트에서 동쪽 땅 M개의 포인트를 연결하고자 하며, N은 M보다 작거나 같다. 이때 강의 동쪽에 연결할 M개의 포인트 중에 N개를 선택하면 서쪽에서 이어질 다리가 교차하면 안 되므로 다리를 짓는 경우가 1개 나온다. 즉 M개의 포인트에서 N개를 선택하는 경우의 수가 이 문제의 정답이다. 

조합의 갯수를 구하는 문제이다.

주의할점

조합은 수가 커질수록 결괏값이 커지므로 수의 범위를 조심해야 한다. 문제에서는 M, N의 최댓값이 30이기 때문에 나올 수 있는 수의 최댓값은 155117520으로 int범위를 벗어나지 않는다. Python3부터는 int값 이상도 표현할 수 있지만 다른 언어로 작성하면 combination을 구할 숫자가 커질 때 주의가 필요하다.

---

코드

N = int(input())
 
for _ in range(N):
    n, m = map(int, input().split())
    bigNum = 1
    smallNum = 1
    while n >= 1:
        bigNum *= m
        smallNum *= n
        m -= 1
        n -= 1
    print(bigNum // smallNum)

 

주석 추가

N = int(input())
 
for _ in range(N):
    n, m = map(int, input().split())  # M, N 입력
    bigNum = 1  # (M-N)!이 될 수
    smallNum = 1  # N!이 될 수
    while n >= 1:  # N이 1이될때까지 bigNum에 M, smallNum에 N을 곱하고 1씩 뺀다
        bigNum *= m
        smallNum *= n
        m -= 1
        n -= 1
    print(bigNum // smallNum)
 

---

채점 결과