백준 1010. 다리 놓기 (파이썬)

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

해설

이 문제는 고등학교 수학에서 배웠던 "조합"을 이용해서 풀 수 있다.

조합은 순서에 상관없이 서로 다른 n개 중에 r개를 선택하는 경우의 수를 구할 때 사용한다. 또한 이 문제는 중복이 불가능하다고 명시되어 있으므로 중복 조합을 사용하지 않고, 그냥 조합을 사용한다. 조합 공식은 아래와 같다.

조합 공식 (출처 : https://coding-factory.tistory.com/606)

n!은 n * (n-1) * (n-2) * ... * 1 과 같이 1을 감소시키며 곱하는 것으로 재귀를 활용해서 구현할 수 있다. n값이 1이 되었을 때 재귀를 종료시켜주면 된다.

 

코드

T = int(input()) # (1)


def factorial(b: int) -> int:
    if b <= 1:
        return 1
    return b * factorial(b-1) # (2)


for _ in range(0, T):
    N, M = map(int, input().split()) 
    result = factorial(N) / (factorial(N - M) * factorial(M)) if N > M else factorial(M) / (factorial(M - N) * factorial(N)) # (3)
    print(int(result))

(1) input()으로 사용자로부터 입력을 받게 되면, string 형태로 입력이 들어오게 되므로 int로 바꿔주는 작업이 필요하다.

(2) 파라미터로 받은 b의 값을 1씩 줄여주면서 재귀함수를 호출한다. 그리고 b의 값이 1이 되면 재귀를 종료해준다.

(3) 조합 공식을 재귀로 표현해 놓은 식이다. N의 값이 M보다 작으면 음수 값이 들어가게 되므로, 이를 방지하기 위해서 if 조건을 넣어준다.