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

문제) 재원이는 한 도시의 시장이 되었다.

 

이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다.

 

 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다.

 

강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다.

 

재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고

 

동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

 

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.

 

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

 

재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다.

 

다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라

 

이번 문제의 풀이 방식은 m개의 지역에 n개의 다리를 놓을 수 있는 경우의 수로

 

팩토리얼(m! / (m-n)!*n!)을 이용하여 푸는 방식으로 내장함수 사용과 외장함수 사용으로 2가지로 나뉜다.

 

-내장함수 사용

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

T = int(input())

for _ in range(T):
    a, b = map(int,input().split())
    bridge = fac(b) // (fac(a) * fac(b - a))	# 팩토리얼(nCr)을 이용
    print(bridge)

내장함수 방법은 처음 def를 사용하여 함수를 선언한다.

fac(n)에서 처음 num = 1을 선언하고, 반복문을 통해 1부터 n + 1까지 반복하여

 

num과 i를 곱한 후 num을 반환합니다.

 

이 후 T를 입력값을 선언하고, 반복문을 만들어 T번 반복하고,

 

a, b를 입력받아 팩토리얼 공식을 넣어 출력하면 된다.

 

- 외장함수 사용

# math 외장함수 사용

import math

T = int(input())

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

외장함수는 math를 가져와 사용하는 것으로 처음 T를 입력하고 for문을 이용해 반복하는 것은 같다.

 

그러나 팩토리얼 공식을 선언할 때 외장함수를 선언하였기 때문에 math.factorial을 선언해주어야 한다.

 

이번 문제는 쉬운 듯하면서 어려웠다.....

 

이해가 안되시거나 틀린 정보는 댓글로 알려주시면 감사하겠습니다!