[구현/수학] 백준 1010 다리 놓기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1010번: 다리 놓기

 

 

 

2. 문제 풀이

 다리를 놓을 수 있는 경우의 수를 구하는 문제입니다. 다리를 겹쳐서 놓지는 못하며, 강 서쪽(N)보다 강 동쪽(M)에 다리를 놓을 수 있는 장소가 항상 많습니다. 

 

 어렵게 생각하면 끝도 없이 어렵지만, 단순하게 생각하면 쉽습니다. 강 동쪽에서 1, 3, 6, 7번에 다리를 놓는다고 합시다. 그러면 강 서쪽은 어떻게 될까요?

 

 위와 같은 경우, 단 1가지 밖에 없습니다. N개의 다리를 놓아야 하며, 서로 겹쳐지면 안되기 때문에 1가지 경우로 축약됩니다. 따라서 M개 중에 N개를 뽑을 조합의 수와 같습니다.

 

 

 

3. 코드

from math import comb
import sys
input = sys.stdin.readline

#입력
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    print(comb(M, N))

 파이썬의 comb 함수를 이용하면 쉽게 조합을 구할 수 있습니다. 

 

2022.03.11 - [Algorithm] - [수학/DP] 백준 2407 조합 - 파이썬(Python)

[수학/DP] 백준 2407 조합 - 파이썬(Python)

 만약 직접 구현하고 싶다면, DP를 이용해서 효율적으로 조합을 구하실 수 있습니다.