[python] Baekjoon 1010 : 다리 놓기

문제 - Baekjoon 1010 : 다리 놓기

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

1010번: 다리 놓기

핵심

서쪽 사이트 N개와 동쪽 사이트 M개를 연결하는 다리를 지을 수 있는 경우의 수 계산.

내용

이 문제는 동쪽과 서쪽에 있는 사이트를 연결하는 다리를 지을 때, 겹치지 않게 다리를 지을 수 있는 모든 경우의 수를 구하는 조합 문제입니다. 다리는 각 사이트에 최대 한 개만 연결되며, 서쪽의 N개 사이트를 모두 사용하여 동쪽의 M개 사이트와 연결해야 합니다.

코드 화면 - (DALLE)

접근 방법

이 문제는 다리를 짓는 방법의 수를 구하는 것과 같으며, 간단히 말해 조합(combinations) 문제입니다. 서쪽의 N개 사이트와 동쪽의 M개 사이트가 있다고 할 때, 동쪽의 M개 사이트 중에서 N개를 고르는 경우의 수와 같습니다.

 

팩토리얼을 계산하는 함수와 조합을 구하는 공식을 사용하여 문제를 해결할 수 있습니다. 팩토리얼 함수는 주어진 수에서부터 1까지 모든 수를 곱하는 함수입니다. 예를 들어, 5!=5×4×3×2×15!=5×4×3×2×1. 조합 함수는 이 팩토리얼 함수를 이용해, 주어진 M개 중 N개를 선택하는 경우의 수를 계산합니다.

코드

1. 라이브러리 미사용

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

def combination(m, n):
    return factorial(m) // (factorial(n) * factorial(m-n))

T = int(input())  # 테스트 케이스 개수
for _ in range(T):
    N, M = map(int, input().split())
    print(combination(M, N))

2. 라이브러리 사용

from math import comb

T = int(input()) # 테스트 케이스의 수
for _ in range(T):
N, M = map(int, input().split())
print(comb(M, N))

풀이

라이브러리 미사용 풀이

팩토리얼 함수 factorial은 재귀를 이용해 구현합니다.

서쪽 사이트 N개와 동쪽 사이트 M개를 연결하는 경우의 수는 C(M,N)으로 계산합니다.

재귀 호출을 통해 팩토리얼을 계산하고, 이를 통해 조합의 값을 구하여 출력합니다.

라이브러리 사용 풀이

`comb(M, N)` 함수는 M개 중에서 N개를 선택하는 조합의 수를 반환합니다.

각 테스트 케이스에 대해 주어진 N과 M에 대한 조합의 수를 계산하여 출력합니다.

 

책읽는 사람

참고 자료

- 파이썬 조합 계산 방법: [Python math.comb](https://docs.python.org/3/library/math.html#math.comb))
- 조합과 순열의 기본 개념: [Combinations and Permutations](https://en.wikipedia.org/wiki/Combination))